// UVa 10816 - Travel in Desert #include <iostream> #include <string.h> #include <algorithm> #include <stdio.h> using namespace std; #define MaxN 101 int color[MaxN], cnt[MaxN], first[MaxN], next[MaxN]; struct edge { int a, b; double t, l; }; bool by_t(edge a, edge b) { return a.t < b.t; } void paint(int ca, int cb) { int a; for (a = first[ca]; next[a] != 0; a = next[a]) color[a] = cb; color[a] = cb; next[a] = first[cb]; first[cb] = first[ca]; cnt[cb] += cnt[ca]; cnt[ca] = 0; } double lnk[MaxN][MaxN]; int from[MaxN]; int n, m, s, t; double dijkstra() { // init double cost[MaxN]; for (int i = 1; i <= n; i++) cost[i] = -1; cost[s] = 0; bool yet[MaxN]; memset(yet, true, sizeof(yet)); // main int nxt = s; while (nxt != t && nxt != -1) { int now = nxt; yet[now] = false; nxt = -1; for (int i = 1; i <= n; i++) if (yet[i]) { if (lnk[now][i] != -1 && (cost[i] == -1 || cost[i] > cost[now] + lnk[now][i])) { cost[i] = cost[now] + lnk[now][i]; from[i] = now; } if (cost[i] != -1 && (nxt == -1 || cost[i] < cost[nxt])) nxt = i; } } return cost[t]; } void print(int i) { if (i != s) { print(from[i]); cout << " " << i; } else cout << i; } int main() { while (cin >> n >> m) { cin >> s >> t; edge e[10000]; for (int j = 0; j < m; j++) cin >> e[j].a >> e[j].b >> e[j].t >> e[j].l; sort(e, e + m, by_t); for (int i = 1; i <= n; i++) { color[i] = i; cnt[i] = 1; first[i] = i; next[i] = 0; } // init cost for (int i = 1; i < n; i++) for (int j = i; j <= n; j++) { lnk[i][j] = -1; lnk[j][i] = -1; } // double sol_t = 0; int k = 0; for (int j = 0; j < m; j++) { // update cost if (lnk[e[j].a][e[j].b] == -1 || e[j].l < lnk[e[j].a][e[j].b]) { lnk[e[j].a][e[j].b] = e[j].l; lnk[e[j].b][e[j].a] = e[j].l; } // update colors int ca = color[e[j].a]; int cb = color[e[j].b]; if (ca != cb) { if (cnt[ca] < cnt[cb]) paint(ca, cb); else paint(cb, ca); } if (color[s] == color[t]) { sol_t = e[j].t; k = j; break; } } for (int j = k + 1; j < m && e[j].t == e[j - 1].t; j++) { // update cost if (lnk[e[j].a][e[j].b] == -1 || e[j].l < lnk[e[j].a][e[j].b]) { lnk[e[j].a][e[j].b] = e[j].l; lnk[e[j].b][e[j].a] = e[j].l; } } // min path double sol_l = dijkstra(); // output print(t); cout << endl; printf("%.1f %.1f\n", sol_l, sol_t); } return 0; }
Tuesday, September 29, 2015
UVa 10816 - Travel in Desert
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment