本文共 1486 字，大约阅读时间需要 4 分钟。
#include#include #include #include using namespace std;struct node{ int a,b,w;}s[50010];int dis[50010];int path[50010];int in[50010];int out[50010];int ans;void Bellman(int n,int m){ memset(path,0,sizeof(path)); memset(dis,0,sizeof(dis)); for(int j = 2; j <= n; j++) { bool flag = false; for(int i = 1;i<=m;i++) { if((dis[s[i].a] < dis[s[i].b] + s[i].w) || ((dis[s[i].a] == dis[s[i].b]+s[i].w)&& s[i].b < path[s[i].a])) { dis[s[i].a] = dis[s[i].b]+s[i].w; path[s[i].a] = s[i].b; flag = true; } } if(!flag)break; } printf("%d\n",dis[ans]); int k = ans; while(path[k]!=0) { printf("%d %d\n",k,path[k]); k = path[k]; }}int main(){ int n,m; int i; while(~scanf("%d %d", &n,&m)) { memset(s,0,sizeof(s)); memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); for(i = 1;i <= m; i++) { scanf("%d %d %d", &s[i].a,&s[i].b,&s[i].w); in[s[i].b]++; out[s[i].a]++; } for(i = 1;i <= n; i++) { if(in[i] == 0) ans = i; } Bellman(n,m); } return 0;}/***************************************************User name: rj170408宋博文Result: AcceptedTake time: 732msTake Memory: 1564KBSubmit time: 2018-07-26 16:32:20****************************************************/
转载地址：http://tnwtb.baihongyu.com/