http://ac.jobdu.com/problem.php?pid=1008
这道题告诉我们 INT_MAX, 慎用，dijkstra 有时加溢出了，你都不知道
#include <cstdio> //#include <climits> #include <algorithm> using namespace std; #define rep(i,j,k) for(int i=j;i<=k;i++) #define inone(i) scanf("%d",&i) #define intwo(i,j) scanf("%d%d",&i,&j) #define infour(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d) #define INT_MAX 9999999 const int maxn = 1e3 + 10; int dis[maxn][maxn], prc[maxn][maxn], v[maxn], D[maxn], P[maxn], s, t, n, m, a, b, d, p; void dij(int s, int t) { fill(D, D + maxn, INT_MAX); fill(P, P + maxn, INT_MAX); fill(v, v + maxn, false); D[s] = 0; P[s] = 0; rep(i, 1, n) { int tnode = s, minD = INT_MAX, minPrc = INT_MAX; rep(j, 1, n) { if (v[j]) continue; if (D[j] < minD ||(D[j] == minD && P[j] < minPrc)) { minD = D[j]; tnode = j; minPrc = P[j]; } } v[tnode] = true; if (tnode == t) return; rep(j, 1, n) { if (v[j]) continue; if (dis[tnode][j] + D[tnode] < D[j] ||(dis[tnode][j] + D[tnode] == D[j] && prc[tnode][j] + P[tnode] < P[j])) { D[j] = dis[tnode][j] + D[tnode]; P[j] = prc[tnode][j] + P[tnode]; } } } } int main() { while (intwo(n,m) != EOF) { if (m == 0 && n == 0) break; rep(i, 1, n) rep(j, 1, n) dis[i][j] = prc[i][j] = INT_MAX; rep(i, 1, m) { infour(a, b, d, p); dis[a][b] = dis[b][a] = d; prc[a][b] = prc[b][a] = p; } intwo(s, t); dij(s, t); printf("%d %d\n", D[t],P[t]); } return 0; }
