题解 P2299 【Mzc和体委的争夺战】

· · 题解

本来认为是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;
}

//蒟蒻题解，多多指教