1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<queue> 6 using namespace std; 7 const int inf=1<<29; 8 const int maxn=1100; 9 const int maxm=maxn*maxn; 10 int e,pnt[maxm],head[maxn],nxt[maxm],cost[maxm]; 11 int dist[maxn],pre[maxn],cnt[maxn]; 12 int n,m; 13 bool vis[maxn]; 14 queue<int> q; 15 void add(int u,int v,int c) 16 { 17 pnt[e]=v; 18 nxt[e]=head[u]; 19 cost[e]=c; 20 head[u]=e++; 21 } 22 bool Spfa(int st) 23 { 24 for(int i=0; i<=n; i++) 25 dist[i]=inf; 26 dist[st]=0; 27 q.push(st);//入队 28 while(!q.empty())//循环一直到空 29 { 30 int u=q.front();//队顶 31 q.pop();//出队 32 vis[u]=0;//标记已经出队； 33 for(int i=head[u]; i!=-1; i=nxt[i])//与顶点为u所连接的点进行松弛 34 if(dist[pnt[i]]>dist[u]+cost[i]) 35 { 36 pre[pnt[i]]=u;//把该点前驱 记录下来 37 dist[pnt[i]]=dist[u]+cost[i];//进行松弛操作 38 if(!vis[pnt[i]])//不在队中 39 { 40 if(++cnt[pnt[i]]==n)//假如某点一直进队，就一直被松弛，松弛次数大于等于n时，则存在负权回路 41 return true; 42 q.push(pnt[i]);//入队 43 vis[pnt[i]]=1;//标记在队中 44 } 45 } 46 } 47 return false; 48 } 49 void DFS(int u) 50 { 51 if(pre[u]==-1) 52 { 53 printf("%d",u); 54 return; 55 } 56 DFS(pre[u]); 57 printf("->%d",u); 58 } 59 int main() 60 { 61 while(~scanf("%d%d",&n,&m))//点数，边数 62 { 63 e=0; 64 memset(head,-1,sizeof(head)); 65 memset(cnt,0,sizeof(cnt));//判断是否有负权回路 66 memset(pre,-1,sizeof(pre));//存路径（前缀） 67 memset(vis,0,sizeof(vis));//标记该数是否已经在队里了 68 while(m--) 69 { 70 int u,v,c; 71 scanf("%d%d%d",&u,&v,&c); 72 add(u,v,c); 73 add(v,u,c); 74 } 75 if(Spfa(1)) 76 printf("-1 "); 77 else 78 { 79 for(int i=2; i<=n; i++) 80 { 81 printf("sss %d %d ",i,dist[i]); 82 DFS(i); 83 printf(" "); 84 } 85 } 86 } 87 }
测试数据
7 12
1 2 24
1 3 8
1 4 15
2 5 6
3 5 7
3 6 3
4 7 4
5 7 9
6 5 2
6 7 3
6 4 5
7 2 3