过路费 （最短路）

发表于 |
字数统计: 1,201字 | 阅读时长 ≈ 6min

过路费

问题描述

有一天你来到了一个奇怪的国家，它有 N 个城市，城市之间有若干条双向道路连接，每条道路都有一定的费用，经过城市也要一定的费用。从一个城市到达另一个城市的总花费为路径上费用最大的城市费用（包括起点和终点）加上路径上所有的道路的费用。给出 Q 次询问，分别回答每次询问中两城市间的最少花费。保证城市之间可以互达。

输入格式

第一行两个整数 N，M，表示有 N 个城市 M 条道路。
接下来 N 行每行一个整数，表示城市的费用 ci。
接下来 M 行每行三个整数，x，y，z，表示城市 x 和城市 y 间有一条费用为 z 的道路。
接下来一行一个整数 Q，表示询问次数。
接下来 Q 行每行两个整数 x，y（x 不等于 y），表示询问从城市 x 到城市 y 的最小花费。

输出格式

共 Q 行每行一个整数，第 i 行的整数表示第 i 次询问的答案。

样例输入

3 3
1
3
2
1 2 1
2 3 1
1 3 3
2
1 3
1 3

样例输出

5
5

数据规模

对于 30%的数据，N<=10，M<=20，Q<=5。
对于 60%的数据，N<=200，M<=4000，Q<=100。
对于 100%的数据，N<=300，M<=40000，Q<=100000，1<=ci<=100000，1<=z<=1000。

鉴于n这么小，当然要枚举最大点权。

做法一：改进floyd
注意到floyd算法的三层循环，那么假设外层为$k$，内层为$i,j$，那么此时经过的点必定属于${1,2,3,…,k} \bigcup {i，j}$中，那么如果将点权排序，则当前算出的最短路中最大点权一定是$i,j,k$中的一个。

由此只需要在floyd中加入一个$ans[i][j]$表示所求答案，得到转移
$ans[i][j]=min{ans[i][j],map[i][k]+map[k][j]+max(c[i],c[j],c[k])}$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 305
using namespace std;
struct node{int x,y;}B[N];
bool cmp(node a,node b)
{return a.x<b.x;}
int n,m,q,C[N],id[N],map[N][N],ans[N][N];
int main()
{
	int i,j,k,x,y,z;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&C[i]);
		B[i].x=C[i];
		B[i].y=i;
	}
	sort(B+1,B+n+1,cmp);
	for(i=1;i<=n;i++)id[B[i].y]=i;
	memset(ans,10,sizeof(ans));
	memset(map,10,sizeof(map));
	for(i=1;i<=n;i++)map[i][i]=0;
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		x=id[x];y=id[y];
		map[x][y]=map[y][x]=min(z,map[x][y]);
	}
	for(k=1;k<=n;k++)
	for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
	{
		map[i][j]=min(map[i][j],map[i][k]+map[k][j]);
		ans[i][j]=min(ans[i][j],map[i][j]+max(B[i].x,max(B[j].x,B[k].x)));
	}
	scanf("%d",&q);
	while(q--)
	{
		scanf("%d%d",&x,&y);
		x=id[x];y=id[y];
		printf("%d\n",ans[x][y]);
	}
}

做法二：一般最短路算法

既然要枚举最大点权，那么大于枚举的点权的点不走即可，那么从枚举的点出发跑单源最短路，然后同样用
$ans[i][j]=min{ans[i][j],map[i][s]+map[s][j]+c[s]}$转移即可。

由于两点之间的最短路上每一个点都会被讨论到，所以正确性是显然的。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#define N 305
#define M 100005
using namespace std;
int n,m,C[N],ans[N][N];
int TOT,LA[N],NE[M],EN[M],LE[M];
int dis[N];
bool mark[N];
queue<int>Q;
void ADD(int x,int y,int z)
{
	TOT++;
	EN[TOT]=y;
	LE[TOT]=z;
	NE[TOT]=LA[x];
	LA[x]=TOT;
}
void SPFA(int s)
{
	int i,j,x,y;
	memset(dis,60,sizeof(dis));
	dis[s]=0;mark[s]=1;Q.push(s);
	while(Q.size())
	{
		x=Q.front();
		Q.pop();
		mark[x]=0;
		for(i=LA[x];i;i=NE[i])
		{
			y=EN[i];
			if(C[y]>C[s])continue;
			if(dis[y]>dis[x]+LE[i])
			{
				dis[y]=dis[x]+LE[i];
				if(!mark[y])mark[y]=1,Q.push(y);
			}
		}
	}
	for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)ans[i][j]=min(ans[i][j],dis[i]+dis[j]+C[s]);
}
int main()
{
	int i,j,k,x,y,z;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)scanf("%d",&C[i]);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		ADD(x,y,z);ADD(y,x,z);
	}
	memset(ans,60,sizeof(ans));
	for(i=1;i<=n;i++)SPFA(i);
	scanf("%d",&k);
	while(k--)
	{
		scanf("%d%d",&x,&y);
		printf("%d\n",ans[x][y]);
	}
}