题意 ： 中文题不详述。
思路 ：无论是SPFA还是Dijkstra都在更新最短路的那个地方直接将花费更新了就行，还有别忘了判重边，话说因为忘了判重边WA了一次。
1 //3790 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 #include <queue> 7 const int INF = 1 << 28 ; 8 9 using namespace std; 10 11 int n, m,s,t; 12 int cost[1100][1100] ,mapp[1100][1010]; 13 int dist[1100],cost1[1100] ; 14 int vis[1100] ; 15 16 void spfa(int src) 17 { 18 queue<int> Q ; 19 memset(vis,0,sizeof(vis)) ; 20 for(int i = 1 ; i <= n ; i++) 21 { 22 dist[i] = INF ; 23 cost1[i] = INF ; 24 } 25 dist[src] = 0 ; 26 vis[src] = 1 ; 27 cost1[src] = 0; 28 Q.push(src) ; 29 while(!Q.empty()) 30 { 31 int u = Q.front() ; 32 Q.pop() ; 33 vis[u] = 0; 34 for(int i = 1 ; i <= n ; i++) 35 { 36 37 if(dist[i] > dist[u] + mapp[u][i]) 38 { 39 dist[i] = dist[u] + mapp[u][i] ; 40 cost1[i] = cost1[u] + cost[u][i] ; 41 if(!vis[i]) 42 { 43 vis[i] = 1 ; 44 Q.push(i) ; 45 } 46 } 47 else if(dist[i] == dist[u]+mapp[u][i]) 48 { 49 if(cost1[i] > cost1[u] + cost[u][i]) 50 { 51 cost1[i]=cost1[u] + cost[u][i]; 52 if(!vis[i]) 53 { 54 vis[i] = 1 ; 55 Q.push(i) ; 56 } 57 } 58 59 } 60 } 61 } 62 } 63 void Init() 64 { 65 for(int i = 1 ; i <= n ; i++) 66 for(int j = 1 ; j <= n ; j++) 67 { 68 if(i == j) mapp[i][j] = cost[i][j] = 0 ; 69 else mapp[i][j] = cost[i][j] = INF ; 70 } 71 } 72 int main() 73 { 74 // 75 while(cin >> n >> m) 76 { 77 if(n == 0 && m == 0) break ; 78 int a, b , d , p ; 79 Init() ; 80 for(int i = 0 ; i < m ; i++) 81 { 82 cin >> a >> b >> d >> p ; 83 if(mapp[a][b] > d) 84 { 85 mapp[a][b] = mapp[b][a] = d ; 86 cost[a][b] = cost[b][a] = p ; 87 } 88 else if(mapp[a][b] == d&&cost[a][b] > p) 89 cost[a][b] = cost[b][a] = p ; 90 } 91 cin >> s >> t ; 92 spfa(s) ; 93 printf("%d %d\n",dist[t],cost1[t]) ; 94 } 95 return 0; 96 }
会神的Dijkstra
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define maxn 1001 5 using namespace std; 6 const int inf=1<<28; 7 8 int g[maxn][maxn]; 9 int cost[maxn][maxn]; 10 int n,m,a,b,d,p,s,e; 11 bool vis[maxn]; 12 int dis[maxn],c[maxn]; 13 14 void inti() 15 { 16 for(int i=1; i<=n; i++) 17 { 18 for(int j=1; j<=n; j++) 19 { 20 if(i==j) 21 { 22 g[i][j]=0; 23 cost[i][j]=0; 24 } 25 else 26 { 27 g[i][j]=inf; 28 cost[i][j]=inf; 29 } 30 } 31 } 32 } 33 34 void dijkstra(int str) 35 { 36 memset(vis,false,sizeof(vis)); 37 for(int i=1; i<=n; i++) 38 { 39 dis[i]=g[str][i]; 40 c[i]=cost[str][i]; 41 } 42 dis[str]=0; 43 c[str]=0; vis[str]=true; 44 for(int i=1; i<n; i++) 45 { 46 int m=inf,x; 47 for(int y=1; y<=n; y++) if(!vis[y]&&dis[y]<m) m=dis[x=y]; 48 vis[x]=true; 49 for(int y=1; y<=n; y++) 50 { 51 if(!vis[y]&&g[x][y]!=inf) 52 { 53 if(dis[y]>dis[x]+g[x][y]) 54 { 55 dis[y]=dis[x]+g[x][y]; 56 c[y]=c[x]+cost[x][y]; 57 } 58 else if(dis[y]==dis[x]+g[x][y]) 59 { 60 if(c[y]>c[x]+cost[x][y]) 61 c[y]=c[x]+cost[x][y]; 62 } 63 } 64 } 65 } 66 } 67 int main() 68 { 69 while(scanf("%d%d",&n,&m)!=EOF) 70 { 71 if(n==0&&m==0) break; 72 inti(); 73 for(int i=0; i<m; i++) 74 { 75 scanf("%d%d%d%d",&a,&b,&d,&p); 76 if(d<g[a][b]) 77 { 78 g[a][b]=g[b][a]=d; 79 cost[a][b]=cost[b][a]=p; 80 } 81 82 } 83 scanf("%d%d",&s,&e); 84 dijkstra(s); 85 printf("%d %d\n",dis[e],c[e]); 86 } 87 return 0; 88 }