1 #include
     
        2 using namespace std;  3 #include
      
         4 #define MAXN 10  5 #define INF 100000000  6 struct node  7 {  8     int to;  9     int w; 10     node * next;     11 }; 12  13 node * List[MAXN]; 14 int path[MAXN]; 15 int dist[MAXN]; 16 int vis[MAXN]; 17 int n;  18  19 void SPFA(int v0) 20 { 21         int u; 22         for(int i=0;i
       

q; 33 q.push(v0); 34 35 while(!q.empty()) 36 { 37 u=q.front(); 38 q.pop(); 39 temp=List[u]; 40 while(temp!=NULL) 41 { 42 int v=temp->to; 43 if(dist[v]>dist[u]+temp->w) 44 { 45 dist[v]=dist[u]+temp->w; 46 path[v]=u; 47 if(!vis[v]) 48 { 49 q.push(v); 50 vis[v]++; 51 } 52 } 53 temp=temp->next; 54 } 55 } 56 } 57 void show(int i) 58 { 59 if(i==0) 60 return; 61 show(path[i]); 62 printf("%d->",i); 63 } 64 int main() 65 { 66 scanf("%d",&n); 67 int u,v,w; 68 node* temp; 69 memset(List ,0,sizeof(List)); 70 while(1) 71 { 72 temp=new node; 73 scanf("%d%d%d",&u,&v,&w); 74 if(u==-1&&v==-1&&w==-1) 75 break; 76 temp->next=NULL; 77 temp->to=v; 78 temp->w=w; 79 if(List[u]==NULL) List[u]=temp; 80 else 81 { 82 temp->next=List[u]; 83 List[u]=temp; 84 } 85 } 86 SPFA(0); 87 for(int i=1;i

",0); 91 show(path[i]); 92 printf("%d\n",i); 93 } 94 system("pause"); 95 return 0; 96 } 97 98 /* 99 100 7101 0 1 6102 0 2 5103 0 3 5104 1 4 -1105 2 1 -2106 2 4 1107 3 2 -2108 3 5 -1109 4 6 3110 5 6 3111 -1 -1 -1112 */