自动搬运

查看原文

来自洛谷，原作者为

	xiaolou 有什么写的必要吗

搬运于2025-08-24 21:53:56，当前版本为作者最后更新于2018-10-13 21:57:26，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

2325131433448687~

这道题居然没有floyd的题解，蒟蒻表示愤愤不平，100的数据都没人写floyd，那我就来水一发2333。。。

神奇代码：

#include <bits/stdc++.h>

using namespace std;
int h[105][105],d[105][105];
void floyd(int n)
{
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				h[i][j]=min(h[i][j],h[i][k]+h[k][j]);
}//floyd的板子，floyd的特点就是思路清晰，代码精简，所以很适合我这样听不懂dijkstra和spfa的蒟蒻使用。。。	

int main()
{
	memset(h,0x3f3f3f3f,sizeof(h));//一拜初始化
	int n,m,k;
	cin >> n >> m;
	for(int i=1;i<=m;i++)
	{
		int s,e;
		cin >> s >> e;
		cin >> d[s][e];
		d[e][s]=d[s][e];
		h[s][e]=h[e][s]=0;
	}//二拜建图（注意是双向边，建成单向边会瞬间爆炸。。。）
	cin >> k;
	for(int i=1;i<=k;i++)
	{
		int s,e;
		cin >> s >> e;
		h[s][e]=h[e][s]=d[s][e];//三拜删边(2333)
	}
	floyd(n);//套板子喽！真香。。。
	int st,en;
	cin >> st >> en;
	cout << h[st][en];//愉快地输出，最后祝大家NOIP进复赛！
	return 0;
    //2325131433448687
}