自动搬运

查看原文

来自洛谷，原作者为

	Dr.九命猫 神啊，来吧，到了我俩算总账的时候了

搬运于2025-08-24 21:36:06，当前版本为作者最后更新于2018-02-06 10:15:47，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

本来认为是dijkstra

其实BELLMAN-FORD就抡过去了（划掉）

以下是B-F代码

#include<cstdio>
using namespace std;
int a[1000001],b[1000001],c[1000001],d[2510];
/*注意数组大小，没给范围，100W才过。。。*/
int main()
{
   int n,m;
   int i,j;
   int INF=999999999;
   //INF尽量大，但是要保证2*INF不爆
   scanf("%d%d",&n,&m);
   for(i=1;i<=m;i++)
   {
   	scanf("%d%d%d",&a[i],&b[i],&c[i]);
   }
   for(i=1;i<=n;i++)
   {
   	if(i==1) d[i]=0;
   	else d[i]=INF;
   }//赋初值
   for(i=1;i<=n-1;i++)
   {
   	for(j=1;j<=m;j++)
   	{
   		if(d[a[j]]+c[j]<d[b[j]])
   		d[b[j]]=d[a[j]]+c[j];
           //因为是无向图，所以来回两遍
   		if(d[b[j]]+c[j]<d[a[j]])
   		d[a[j]]=d[b[j]]+c[j];		
   	}//标准的松弛
   }
   printf("%d",d[n]);//题目错了，应该是N不是M
   return 0;
}

//蒟蒻题解，多多指教