1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           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
          
            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\n");77 else78 {79 for(int i=2; i<=n; i++)80 {81 printf("sss %d %d\n",i,dist[i]);82 DFS(i);83 printf("\n");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