最短路径练习题

A - Til the Cows Come Home

史学长很热爱学习，他打算假期偷偷跑回学校学习，为了多学习他希望可以找最快的路线回到学校。 洛阳市里有N个(2 <= N <= 1000)个地铁站，编号分别为1..N。他的家在1号地铁站旁边，洛阳师范学院站是N号地铁站。地铁站之间共有M (1 <= M <= 2000)条双向路径。 史学长现在在1号地铁站，他希望知道到学校最短要多长时间。可以保证史学长能到达学校。忽略史学长在换乘地铁时需要的等待时间。

Input

* 第一行输入两个整数m和n

* 接下来m行，每行三个整数a、b、c，表示a号地铁站和b号地铁站间要花费时间c（1<=c<=100）.

Sample

    Input

5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100

    Output

90

题解：

#include
#include
using namespace std;
int m,n,mapp[1002][1002],vis[1002],dis[1002];
const int inf=0x3f3f3f3f;

int main(){
	cin>>m>>n;
	memset(mapp,inf,sizeof(mapp));
	for(int a,b,c,i=1;i<=m;i++){
		cin>>a>>b>>c;
		mapp[a][b]=min(mapp[a][b],c);
		mapp[b][a]=mapp[a][b];
	}
	for(int i=1;i<=n;i++) dis[i]=mapp[1][i];
	vis[1]=1;
	for(int i=1;i 

B - Frogger 
湖中有n块石头，编号从1到n，有两只青蛙，Bob在1号石头上，Alice在2号石头上，Bob想去看望Alice，但由于水很脏，他想避免游泳，于是跳着去找她。但是Alice的石头超出了他的跳跃范围。因此，Bob使用其他石头作为中间站，通过一系列的小跳跃到达她。两块石头之间的青蛙距离被定义为两块石头之间所有可能路径上的最小必要跳跃距离，某条路径的必要跳跃距离即这条路径中单次跳跃的最远跳跃距离。你的工作是计算Alice和Bob石头之间的青蛙距离。
 
Input
 
多实例输入
 先输入一个整数n表示石头数量，当n等于0时结束。
 接下来2-n+1行依次给出编号为1到n的石头的坐标xi , yi。
 2 <= n <= 200
 0 <= xi , yi <= 1000
 
Output
 
先输出"Scenario #x"， x代表样例序号。
 接下来一行输出"Frog Distance = y"， y代表你得到的答案。
 每个样例后输出一个空行。
 （ps：wa有可能是精度问题，g++不对可以用c++尝试，都不对就是代码问题）
 
Sample Input
 
2
0 0
3 4

3
17 4
19 4
18 5

0
 
Sample Output
 
Scenario #1
Frog Distance = 5.000

Scenario #2
Frog Distance = 1.414
 
题解： 
分析：这里是求所有 路径中的最大跳跃长度（即必要跳跃距离）的最小值。
 
#include //题解1
#include
#include
using namespace std;
int n,x[202],y[202];
double map[202][202];

int main(){
	for(int s=1; ;s++){
		cin>>n;
		if(!n) break;
		for(int i=1;i<=n;i++){
			cin>>x[i]>>y[i];
			for(int j=1;j 
#include //题解2
#include
#include
#include
using namespace std;
int n,x[202],y[202],vis[202];
double map[202][202],dis[203];
const int inf=0x3f3f3f3f;

int main(){
	for(int k=1; ;k++){
		cin>>n;
		if(!n) break;
		memset(vis,0,sizeof(vis));
		for(int i=1;i<=n;i++){
			cin>>x[i]>>y[i];
			for(int j=1;j 

C - Heavy Transportation 
30世纪，X同学领悟了通天大道，开始在各个星球之间穿梭。但因为每次穿梭需要消耗巨大的能量，X同学只好暂时放弃了宇宙遨游的梦想。10年后，他发现每个星球之间的穿梭通道其实隐含着巨大的能量可供飞行，由于X同学天赋异禀，顿悟了吸星大法，他很快踏上了他的宇宙之旅。
 
X同学从地球（1号星球）出发，准备前往遥远的n号星球。因为有强大的力量束缚X同学的能力，X同学只能见到n个星球（1号到n号），且只能在他能力范围内的m个穿梭通道内通行，并用他顿悟的吸星大法吸取其中的全部或部分能量。两个星球之间有且只有一个穿梭通道。
 
由于穿梭通道的能量能给X同学带来难以言喻的爽快感，X同学希望自己在能到达n号星球的所有穿梭通道内，每次获得的能量尽可能大。遗憾的是，吸星大法是很容易走火入魔的。如果X同学在路途中的某一个通道内获得过大的能量，且在接下来的路途中，有通道无法提供与之相等的能量，X同学将倍感空虚，进而损伤道基，这显然是不能被X同学所接受的。当然，X同学也不会选择吸收大于前面任何通道吸收的能量，这将可能导致他爆体而亡。换句话说，X同学每次吸收的能量全部相同。所以，X同学必须提前做好功课，确定好每次能获得的最大能量。
 
Input
 
题目有多组测试数据。
 
第一行给一个 T。
 
每一组数据的第一行给两个数n和m，表示X同学能见的n个星球和能通行的m个穿梭通道。
（1 <= n <= 1000）
 
接下来m行，每行三个数s1，s2，d代表两个星球的编号和它们之间穿梭通道隐含的全部能量。
（1 <= s1，s2 <= n ， 1 <= d <= 1e6）
 
Output
 
每组数据先输出一行 Scenario #k，其中 k 是组别编号（从 1 开始）。
 
下一行输出一个整数，表示X同学每次能获得的最大能量。
 
最后输出一个空行。
 
Sample Input
 
1
3 3
1 2 3
1 3 4
2 3 5
 
Sample Output
 
Scenario #1:
4
 
自己创的样例：
 
Sample Input
 
1
6 9
1 2 1
1 3 12
2 3 9
2 4 3
3 4 4
3 5 5
4 5 13
4 6 15
5 6 4
 
Sample Output
 
Scenario #1:
5
 
题解： 
分析： 与上题相反，这里是求所有路径中的最小长度 的最大值。
 
#include
#include
#include
#include
using namespace std;
int s,n,m,vis[1002],map[1002][1002],dis[1002];
const int inf=0x3f3f3f3f;

int main(){
	cin>>s;
	for(int k=1;k<=s;k++){
		cin>>n>>m;
		memset(map,0,sizeof(map));
		memset(vis,0,sizeof(vis));
		for(int a,b,c,i=1;i<=m;i++){
			cin>>a>>b>>c;
			map[a][b]=c;
			map[b][a]=c;
		}
		for(int i=1;i<=n;i++) dis[i]=map[1][i];
		vis[1]=1;
		for(int i=1;imx){
					mx=dis[j];
					u=j;
				}
			}
			vis[u]=1;
			for(int j=1;j<=n;j++){
				if(!vis[j]&&min(map[u][j],dis[u])>dis[j])
				dis[j]=min(map[u][j],dis[u]);
			}
		}
		cout<<"Scenario #"< 

 D - Silver Cow Party 
德平在他的农场里养了n头牛，每头牛都有一个固定的位置,每天这些牛都要到德平家里参加聚会然后回去，给出n,m,代表牛数+1和有向边数,接着是m条有向边(a,b,c)，代表从牛a到牛b需要花费c秒，给你德平家的位置X（1~n的除x外的编号为牛的位置），每头牛都有一个参加聚会并且回到原来位置的最短时间，从这些最短时间里找出一个最大值输出 N<=1000,M<=100,000,c<=100
 
Input
 
Line 1: 三个整数分别代表: N, M, and X
 Lines 2.. M+1: Line i+1 代表道路i的三个整数：a,b,c
 表示从a到b需要c时间,(不能表示从b到a的时间为c)
 
Output
 
Line 1: 所有 牛最短时间里找出一个 最大值输出
 
Sample Input
 
4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3
 
Sample Output
 
10
 
Hint
 
牛1：去4s，回1s，共5s
 牛3：去6s，回3s，共9s
 牛4：去3s，回7s，共10s
 
题解： 
分析： 单源最短路，求已知点到其他位置的最短路与其他位置到已知点的和的最短路，然后找最大值。（逆向求解）
 
#include
#include
#define maxn 1002
using namespace std;
int n,m,andx,map1[maxn][maxn],map2[maxn][maxn];
int dis[maxn],vis[maxn],sum[maxn],mx;
const int inf=0x3f3f3f3f;
void add(int temp[][maxn]){
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++) dis[i]=temp[andx][i];
	vis[andx]=1;
	for(int i=1;i>n>>m>>andx;
	memset(map1,inf,sizeof(map1));
	memset(map2,inf,sizeof(map2));
	for(int a,b,c,i=1;i<=m;i++){
		cin>>a>>b>>c;
		map1[a][b]=c;
		map2[b][a]=c;
	}
	add(map1);
	for(int i=1;i<=n;i++) sum[i]=dis[i];
	add(map2);
	for(int i=1;i<=n;i++){
		sum[i]+=dis[i];
		if(sum[i]>mx&&i!=andx) mx=sum[i];
	}
	cout< 

E - Currency Exchange 
 
 
我们城市有几个货币兑换点在运作。让我们假设每个点专门针对两种特定货币，并且仅使用这些货币执行交换操作。同一对货币可以有多个点。每个点都有自己的汇率，A对B的汇率是1A的B数量。此外，每个兑换点都有一定的佣金，即您必须为兑换业务支付的金额。佣金总是以来源货币收取。例如，如果你想在汇率为29.75，佣金为0.39的兑换点将100美元兑换成俄罗斯卢布，你将得到（100-0.39）*29.75=2963.3975卢布。你肯定知道在我们城市有N种不同的货币可以交易。让我们为每种货币分配从1到N的唯一整数。然后，每个兑换点可以用6个数字来描述：整数A和B——它兑换的货币数量，以及实际RAB、CAB、RBA和CBA——A兑换B和B兑换A时的汇率和佣金。尼克有一些S币的钱，他想知道在一些兑换业务之后，他是否能以某种方式增加他的资本。当然，他最终还是想把钱换成S货币。帮助他回答这个难题。尼克在做手术的时候必须有一笔非负的钱。
 
Input
 
输入的第一行包含四个数字：N-货币数量，M-兑换点数量，S-尼克拥有的货币数量，V-他拥有的货币单位数量。以下M行各包含6个数字-对应交换点的描述-按上述顺序指定。数字由一个或多个空格分隔。1<=S<=N<=100，1<=M<=100，V是实数，0<=V<=10^3。对于每一点，汇率和佣金都是实数，小数点后最多有两位数字，10^-2<=rate<=10^2，0<=commission<=10^2。如果在这个序列中没有一个兑换点被多次使用，那么让我们将一些兑换操作的序列称为简单的。您可以假设任何简单的交换操作序列的末尾和开头的和的数值比率将小于10^4。（注：多组输入）
 
Output
 
如果Nick可以增加他的财富，则输出YES，在其他情况下，将NO输出到输出文件。
 
Sample Input
 
3 2 1 20.0
1 2 1.00 1.00 1.00 1.00
2 3 1.10 1.00 1.10 1.00
 
Sample Output
 
YES
 
题解： 
 分析：这里是判断正环。
 
#include
#include
using namespace std;
int n,m,s,a,b,u[205],v[205];
double p,a1,a2,b1,b2;
double wh[205],wy[205],dis[105];
int ford(){
	dis[s]=p;
	for(int i=1;i<=n;i++){
		int flag=1;
		for(int j=1;j<=2*m;j++){
			if(dis[v[j]]<(dis[u[j]]-wy[j])*wh[j]){
				dis[v[j]]=(dis[u[j]]-wy[j])*wh[j];
				flag=0;
			}
		}
		if(flag) return 0;
	}
	return 1;
}

int main(){
	cin>>n>>m>>s>>p;
	for(int i=1;i<=m;i++){
		cin>>a>>b>>a1>>b1>>a2>>b2;
		u[2*i-1]=a,v[2*i-1]=b,wh[2*i-1]=a1,wy[2*i-1]=b1;
		u[2*i]=b,v[2*i]=a,wh[2*i]=a2,wy[2*i]=b2;
	}
	if(ford()) cout<<"YES";
	else cout<<"NO";
	return 0;
}
 

F - Wormholes  
题目背景
 
ajil在学习acm的同时也是一个物理学爱好者，他最近迷上了虫洞的研究。
 虫洞非常nb，它是 单向 的，它可以进行时空穿梭旅行，它可以让你到达某个地点的同时回到一段时间之前。
 通过他的超前研究，他用现代科学无法理解的方式在南中附大的校园中发现了很多个虫洞。
 
题目描述
 
南中附大的校园可分为F块区域，每个区域有N（1≤N≤500）栋教学楼被编号为1..N，之间有M（1≤M≤2500）条双向路径，K（1≤K≤200）个虫洞。
 就在昨天，ajil研究虫洞研究的太入迷了，以至于自己的web实训都忘了交，现在他想要通过时间旅行来回到实训提交截止时间之前，
 他会为你提供这F个区域完整的图。所有的路径所花时间都不大于10000秒，所有的虫洞都回到不大于10000秒之前。
 他想知道每块区域是否可以通过时间旅行来回到实训提交截止时间之前，请你帮帮他。
 
Input
 
首先是一个整数F，表示校园被分为了F块区域
 接下来会有F块区域的数据。
 
每组数据第1行：分别是三个空格隔开的整数：N，M和 K
 
第2行到M+1行：三个空格分开的数字（U，V，W）描述教学楼间的双向道路：从U到V需要耗费W秒。两个教学楼可能由一个以上的路径来连接。
 
第M+2到M+K+1行：三个空格分开的数字（U，V，W）描述虫洞：从U到V可以使时间倒流W秒。
 
Output
 
F行，每行对应一块区域。 每块区域输出单独的一行，” YES”表示能满足要求，”NO”表示不能满足要求。
 
Sample Input
 
2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8
 
Sample Output
 
NO
YES
 
题解：  
 分析：这里是判断负环。
 
#include //题解1
#include
using namespace std;
int t;
int n,m,k,map[502][502],dis[502],vis[502];
const int inf=0x3f3f3f3f;
int floyd(){
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(map[i][j]>map[i][k]+map[k][j])
				map[i][j]=map[i][k]+map[k][j];
			}
			if(map[i][i]<0) return 1;
		}
	}
	return 0;
}

int main(){
	cin>>t;
	while(t--){
		cin>>n>>m>>k;
		memset(map,inf,sizeof(map));
		for(int u,v,w,i=1;i<=m;i++){
			cin>>u>>v>>w;
			map[u][v]=min(map[u][v],w);
			map[v][u]=map[u][v];
		}
		int flag=1;
		while(k--){
			int u,v,w;
			cin>>u>>v>>w;
			map[u][v]=-w;
		}
		if(floyd()) cout<<"YES"< 
#include
#include
using namespace std;
int t,n,m,k;
int u[5204],v[5204],w[5204],dis[502];
const int inf=0x3f3f3f3f;
int ford(){
	for(int i=1;i<=n;i++){
		int flag=1;
		for(int j=1;j<=2*m+k;j++){
			if(dis[u[j]]+w[j]>t;
	while(t--){
		cin>>n>>m>>k;
		memset(dis,inf,sizeof(dis));
		dis[1]=0;
		for(int a,b,c,i=1;i<=m;i++){
			cin>>a>>b>>c;
			u[2*i-1]=a,v[2*i-1]=b,w[2*i-1]=c;
			u[2*i]=b,v[2*i]=a,w[2*i]=c;
		}
		for(int a,b,c,i=1;i<=k;i++){
			cin>>a>>b>>c;
			u[2*m+i]=a,v[2*m+i]=b,w[2*m+i]=-c;
		}
		if(ford()) cout<<"YES"< 
#include
#include
#include
using namespace std;
int t,n,m,k;
int map[502][502],dis[502],vis[502],bj[502];
const int inf=0x3f3f3f3f;
queue q;

int spfa(){
	memset(dis,inf,sizeof(dis));
	memset(vis,0,sizeof(vis));
	memset(bj,0,sizeof(bj));
	dis[1]=0;
	q.push(1);
	bj[1]++;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=1;i<=n;i++){
			if(dis[i]>dis[u]+map[u][i]){
				dis[i]=dis[u]+map[u][i];
				if(!vis[i]){
					vis[i]=1;
					bj[i]++;
					if(bj[i]>=n) return 1;
					q.push(i);
				}
			}
		}
	}
	return 0;
}

int main(){
	cin>>t;
	while(t--){
		cin>>n>>m>>k;
		memset(map,inf,sizeof(map));
		for(int u,v,w,i=1;i<=m;i++){
			cin>>u>>v>>w;
			map[u][v]=min(map[u][v],w);
			map[v][u]=map[u][v];
		}
		while(k--){
			int u,v,w;
			cin>>u>>v>>w;
			map[u][v]=-w;
		}
		if(spfa()) cout<<"YES"< 

G - MPI Maelstrom  
 由于叛徒朱子明的出卖，导致独立团在赵家峪的团部驻军在团长李云龙大婚之日几乎全军覆没，突出重围之后，李云龙决定集合所有驻扎在外的部队，使用重型武器意大利炮攻打平安县城，消息从团部传出之后到达各部驻地之后，驻地长官会派出自己的通讯人员通知其他驻地部队，自团部派人传达命令开始，至少经过多长时间才能使得所有驻扎在外的部队受到命令。（假设通讯员在路上不会遭遇任何意外）
 
Input
 
第一行输入一个n，表示包括团部在内有多少不同的驻军（团部当然是编号为1了）。
 随后n-1行，以邻接矩阵的形式给出各驻军（1 ~ n）之间派遣通讯员需要的时间。
 由于两地驻军派遣通讯员所需时间相等（从一营三连驻地到二营一连驻地和二营一连驻地到一营三连驻地所需时间是一样的），且驻地自己和自己不需要派遣通讯员，所以只给出了矩阵的下三角。
 x表示由于部分驻地之间因特殊原因不能派遣通讯员，比如途中需要经过敌占区
 该题所有数据范围0 ~ 100。
 
Output
 
输出一行表示所有驻地都受到来自团部的命令所需要的时间。
 
Sample Input
 
5
50
30 5
100 20 50
10 x x 10
 
Sample Output
 
35
 
题解： 
#include
#include
#include
#include
using namespace std;
int n,map[102][102],dis[102],vis[102];
const int inf=0x3f3f3f3f;
string str;
void spfa(){
	queue q;
	memset(dis,inf,sizeof(dis));
	memset(vis,0,sizeof(vis));
	dis[1]=0;
	q.push(1);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=1;i<=n;i++){
			if(dis[i]>dis[u]+map[u][i]){
				dis[i]=dis[u]+map[u][i];
				if(!vis[i]){
					vis[i]=1;
					q.push(i);
				}
			}
		}
	}
}
void dijkstra(){
	memset(dis,inf,sizeof(dis));
	for(int i=1;i<=n;i++) dis[i]=map[1][i];
	vis[1]=1;
	for(int i=1;idis[u]+map[u][j])
			dis[j]=dis[u]+map[u][j];
		} 
	}
}

int main(){
	cin>>n;
	getline(cin,str);
	memset(map,inf,sizeof(map));
	for(int i=2;i<=n;i++){
		getline(cin,str);
		int x=0,cnt=0;
		for(int j=0;j='0'&&str[j]<='9') x=10*x+str[j]-'0';
			else if(str[j]=='x') x=inf;
			else{
				map[i][++cnt]=x;
				map[cnt][i]=x;
				x=0;
			}
			if(j==str.size()-1) map[i][++cnt]=x,map[cnt][i]=x;
		}
	}
	dijkstra(); //spfa();
	int mx=0;
	for(int i=2;i<=n;i++){
		mx=max(mx,dis[i]);
	}
	cout< 

H - Cow Contest  
没有John和奶牛的模拟赛是不完整的。
 所以John带着他的一群奶牛也来参加程序设计竞赛了。John带了N(1 <= N <= 100)头奶牛参加了场程序设计竞赛。在赛场上，奶牛们按1……N依次编号。每头奶牛的编程能力不尽相同，也就是说，奶牛们的编程能力有明确的排名。 整个比赛被分成了若干轮，每一轮是两头指定编号的奶牛的对决。如果编号为A的奶牛的编程能力强于编号为B的奶牛(1 <= A <= N; 1 <= B <= N; A != B) ，那么她们的对决中，编号为A的奶牛总是能胜出。 John想知道奶牛们编程能力的具体排名，于是他找来了奶牛们所有 M(1 <= M <= 4,500)轮比赛的结果，希望你能根据这些信息，推断出尽可能多的奶牛的编程能力排名。比赛结果保证不会自相矛盾。
 
Input
 
第1行: 2个用空格隔开的整数：N 和 M
 第2..M+1行: 每行为2个用空格隔开的整数A、B，描述了参加某一轮比赛的奶牛的编号，以及结果（编号为A，即为每行的第一个数的奶牛为胜者）
 
Output
 
输出1个整数，表示排名可以确定的奶牛的数目
 
Sample Input
 
5 5
4 3
4 2
3 2
1 2
2 5
 
Sample Output
 
2
 
题解： 
#include
#include
using namespace std;
int n,m,map[102][102],num;
const int inf=0x3f3f3f3f;

int main(){
	cin>>n>>m;
	memset(map,inf,sizeof(map));
	for(int u,v,i=1;i<=m;i++){
		cin>>u>>v;
		map[u][v]=1; 
	}
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(map[i][j]>map[i][k]+map[k][j])
				map[i][j]=map[i][k]+map[k][j];
			}
		}
	}
	for(int i=1;i<=n;i++){
		int j;
		for(j=1;j<=n;j++){
			if(i==j) continue;
			if(map[i][j]==inf&&map[j][i]==inf) break;
		}
		if(j==n+1) num++;
	}
	cout<