简单模版题 敲个ｓｐｆａ还得瞟下模版。。
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<vector> 7 #include<queue> 8 using namespace std; 9 vector<int>ed[910]; 10 #define INF 0xfffffff 11 int dis[910]; 12 int vis[910],g,o[910][910]; 13 int spfa(int e) 14 { 15 memset(vis,0,sizeof(vis)); 16 queue<int>q; 17 for(int i = 1 ; i <= g ; i++) 18 dis[i] = INF; 19 dis[1] = 0; 20 vis[1] = 1; 21 q.push(1); 22 while(!q.empty()) 23 { 24 int u = q.front(); 25 q.pop(); 26 vis[u] = 0; 27 for(int i = 0 ; i < (int)ed[u].size() ;i++) 28 { 29 int v = ed[u][i]; 30 if(dis[v]>dis[u]+o[u][v]) 31 { 32 dis[v] = dis[u]+o[u][v]; 33 if(!vis[v]) 34 { 35 vis[v] = 1; 36 q.push(v); 37 } 38 } 39 } 40 } 41 return dis[e]; 42 } 43 int main() 44 { 45 int i,j,n,k,m,u,t; 46 char c[5]; 47 cin>>n; 48 g = 1;t=0; 49 for(i = 1; i <= 901 ;i++) 50 for(j = 1; j <= 901 ; j++) 51 if(i!=j) 52 o[i][j] = INF; 53 for(i = 1; i <= n ;i ++) 54 { 55 cin>>m; 56 for(j =1; j <= m ; j++) 57 { 58 g++; 59 while(cin>>k) 60 { 61 if(k==0) 62 break; 63 cin>>u; 64 o[k+t][g] = u; 65 ed[k+t].push_back(g); 66 } 67 } 68 if(i!=n) 69 cin>>c; 70 t = g-m; 71 } 72 int minz = INF; 73 for(i = t+1 ; i <= g ; i++) 74 minz = min(minz,spfa(i)); 75 printf("%d ",minz); 76 return 0; 77 }