算法训练 最短路

#include <iostream>
#include <cstdio>
#include <cstring>
#define max_v 50005
#define max_e 500005
#define INF 0x3f3f3f3f

using namespace std;

struct edge{int from,to,cost;};
edge ee[max_e];//存储每条边的信息
int d[max_v];//表示s到每个顶点的最短距离
int v,e;//顶点数和边数

//返回true计算最短路成功，返回false存在负圈；
bool bellman(int s){
    memset(d,INF,sizeof(d));//赋最大值的技巧
    d[s]=0;
    int j=0;//添加的计数器
    while(true){
        bool update=false;
        for(int i=0;i<e;i++){
            edge et=ee[i];
            if(d[et.from]!=INF&&d[et.to]>d[et.from]+et.cost){
                d[et.to]=d[et.from]+et.cost;
                update=true;
            }
        }
        j++;
        if(!update) return true;
        if(j==v) return false;//当进行第v次循环时，说明存在负圈
    }
}


int main()
{
    int x,y,z;
    scanf("%d %d",&v,&e);
    for(int i=0;i<e;i++){
        scanf("%d %d %d",&x,&y,&z);
        x-=1;
        y-=1;
        ee[i].from=x;
        ee[i].to=y;
        ee[i].cost=z;
        ee[e+i].from=y;
        ee[e+i].to=x;
        ee[e+i].cost=z;
    }
    bellman(0);
    for(int i=1;i<v;i++){
        printf("%d\n",d[i]);
    }
    return 0;
}