自动搬运

查看原文

来自洛谷，原作者为

	zjy111 **

搬运于2025-08-24 21:39:04，当前版本为作者最后更新于2019-07-30 09:13:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这是绿名蒟蒻第二次发题解（第一次没有通过）......

一道相对简单的省选题（最短路模板题）也是我AC的第一道绿题

每两个城市之间的时间由地形和有无魔法石决定，而每个地形通过的时间是固定的（2,6,4,8,6,10,14），输入了魔法石的有无，所以时间就出来了。

众所周知，最短路算法很多，这里我选用了Floyd算法（时复N^3），我觉得比较好懂，代码也简单（城市编号不超过100，这不是明显暗示用Floyd吗）反正我连Dijkstra都不会

以下是Floyd具体思路：

用dis[i][j]数组表示i~j的最短路径，从1~n枚举中间点k，如果从i到j过k有更短的路径就刷新，否则保留原来路径（有点动规思想，转移方程：dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j])）

注意事项： 1 循环时要把中间点k放在最外层； 2 一开始时（输入前）每两个点之间都是没有路的，所以距离要标成无限而不是0，否则会导致所有点之间的距离都是0 3 这种算法只适用于无负环图（也就是不存在边权值和＜0的环）不过好像和这题没有关系

献上码风奇特的代码（有一些注释，不过我语文不太好，还请见谅）

#include <bits/stdc++.h>
using namespace std;
unsigned long long i,j,k,x,y,c,dist[105][105];//这个数组记录距离 
int s[8]={99999,2,6,4,8,6,10,14};//这个数组记录每个地形花费时间(我习惯从1开始,所以s[0]要空出) 
bool ck[8];//判断有没有石头 
int main(){
	memset(dis,100000,sizeof(dis));//初始化:必须足够大(即一开始最短路是无限长) 
	for(i=1;i<8;i++)cin>>ck[i]; 
	cin>>x>>y>>c;//x起点,y终点(我更习惯用变量i,j写for循环) 
	if(x==y){ //特判:如果x,y相等就是0!!!!(第一次提交WA了9号点,就因为这个) 
		cout<<0;
		return 0;
	}
	while(c--){
		cin>>i>>j>>k;
		if(ck[k]){ //有石头,花费减半 
			dis[i][j]=s[k]/2;
			dis[j][i]=s[k]/2;//注意这里是双向边,所以两头都要记录	
		}
		else { //没石头,花费照常 
			dis[i][j]=s[k];
			dis[j][i]=s[k];
		}
	}
	for(k=1;k<=100;k++){ //Floyd核心代码,具体思路见上(注意中间点循环放最外层) 
		for(i=1;i<=100;i++){
			for(j=1;j<=100;j++){
				dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
			}
		}
	}
	cout<<dis[x][y]<<endl;//最后输出从x到y最短路距离 
	return 0;
}