http://acm.hdu.edu.cn/showproblem.php?pid=3790
题意：多了一个花费的限制条件，距离相等则选花费少的。
思路：直接在原来的判断条件上加就行，不要想太多。注意有重边。
#include <stdio.h> #include <algorithm> #include <stdlib.h> #include <string.h> #include <iostream> #include <queue> using namespace std; typedef long long LL; const int N = 1005; const int INF = 0x3f3f3f3f; int dis[N], cost[N], G1[N][N], G2[N][N], n; bool vis[N]; void dijkstra(int s) { for(int i = 1; i <= n; i++) { dis[i] = INF; cost[i] = INF; } dis[s] = 0; cost[s] = 0; for(int i = 1; i <= n; i++) { int k = -1; for(int j = 1; j <= n; j++) { if(!vis[j] && (k==-1 || dis[j]<dis[k] || (dis[j]==dis[k]&&(cost[j]<cost[k])))) k = j; } if(k == -1) break; vis[k] = true; for(int j = 1; j <= n; j++) { if(!vis[j] && (dis[k]+G1[k][j]<dis[j] || (dis[k]+G1[k][j]==dis[j]&&(cost[k]+G2[k][j]<cost[j])))) { dis[j] = dis[k]+G1[k][j]; cost[j] = cost[k]+G2[k][j]; } } } } void spfa(int s) { queue<int>que; for(int i = 1; i <= n; i++) { dis[i] = INF; cost[i] = INF; } dis[s] = 0; cost[s] = 0; vis[s] = true; que.push(s); while(!que.empty()) { int now = que.front(); que.pop(); vis[now] = false; for(int i = 1; i <= n; i++) { if(dis[now]+G1[now][i]<dis[i] || (dis[now]+G1[now][i]<dis[i]&&(cost[now]+G2[now][i]<cost[i]))) { dis[i] = dis[now]+G1[now][i]; cost[i] = cost[now]+G2[now][i]; if(!vis[i]) { vis[i] = true; que.push(i); } } } } } int main() { // freopen("in.txt", "r", stdin); int m, u, v, s, t, w1, w2; while(~scanf("%d%d", &n, &m)) { if(n == 0 && m == 0) break; memset(vis, false, sizeof(vis)); for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) { if(i == j) { G1[i][j] = 0; G2[i][j] = 0; } else { G1[i][j] = INF; G2[i][j] = INF; } } for(int i = 1; i <= m; i++) { scanf("%d%d%d%d", &u, &v, &w1, &w2); if(w1<G1[u][v] || (w1==G1[u][v]&&w2<G2[u][v])) { G1[u][v] = G1[v][u] = w1; G2[u][v] = G2[v][u] = w2; } } scanf("%d%d", &s, &t); // dijkstra(s); spfa(s); printf("%d %d\n", dis[t], cost[t]); } return 0; }
