编辑代码

#include<stdio.h>
#include<stdlib.h>

int edgeA[10001];//表征两边中的一边
int edgeB[10001];//表示两边中的另一边
int val[10001];//表征边的权重
int d[101];//记录由0出发到达任意一点所用的花费
/**
* 检查经过v到u是否更近
*/
void relax(int u, int v, int w){ 
	if(d[u]==-1) return; //转折点本身不可达
	else if(d[v]==-1) d[v]=d[u]+w; //唯一路径到达
	else d[v] = d[v]>d[u]+w?d[u]+w:d[v]; //多路径可达，取最短路径
}

int main(){
	int n,k,i,j; 

	scanf("%d %d",&n,&k);//输入n,k 
//    n=3;k=3;
	for(i=1;i<=k;i++)//输入G，v
		scanf("%d %d %d",edgeA+i,edgeB+i,val+i);
//    edgeA[1]=1;edgeB[1]=2;val[1]=2;
//    edgeA[2]=1;edgeB[2]=3;val[2]=6;
//    edgeA[3]=2;edgeB[3]=3;val[3]=3;

	//初始距离默认不可达
    for(i=2;i<=n;i++)
        d[i]=-1;
	d[1]=0;//当前点既是目标点

	for(i=1;i<n;i++)//更新n-1次
		for(j=1;j<=k;j++)//遍历所有的边进行relax
			relax(edgeA[j],edgeB[j],val[j]);
	int lastResult = d[n];
	for(j=1;j<=k;j++)//检查是否有负环
		printf("%d ",d[j]);
//		relax(edgeA[j],edgeB[j],val[j]);
	if(lastResult == -1) printf("-1\n");
	else if(lastResult != d[n]) printf("0\n");
	else printf("%d\n",lastResult);
	return 0;
}