?
?
?
?
?
?
?
UVa 515 - King （差分约束系统 + SPFA求带负权最短路）(二)
nf(%d,&m); memset(next,-1,sizeof(next)); tot = 0; ///自己创造一个超级原点，建立与其他点链接的边（使其与其他点相连接） ///因为SPFA没有办法处理不连通的图 for(int i = 0; i <= n; i++){ addEdge(n+1,i,0);///我让点n+1作为一个超级源点，其余各节点的边权是0 } for(int i = 1; i <= m; i++){ scanf(%d%d%s%d,&si,&ni,oi,&ki); if(oi[0] == 'g') addEdge(si+ni,si-1,-(ki+1)); if(oi[0] == 'l') addEdge(si-1,si+ni,ki-1); } if (spfa(n + 2)) printf(lamentable kingdom );///总共有n+2个点 else printf(successful conspiracy ); } return 0; }
?