POJ 2679 - Adventurous Driving

http://poj.org/problem?id=2679

概要

N 個の街を M 本の道が繋いでいる．

道は長さを持ち，双方向に進むことができるが方向によって異なるコストが設定されている．

このとき，街 A から街 B へ optimal path を通って行ったときのコストの合計と道程を答える．

optimal path とは，経路上のすべての道が rewarding で，かつコストの合計が最小の path の中で道程が最小の path である．

街 X から街 Y へのコスト c の道が rewarding であるとは，街 X に繋がっている道のコストの最小値が c であることである．

ただし，A から B への optimal path が存在しないときは「VOID」と答え，コストの合計の最小が負の無限大であるときは「UNBOUND」と答える．

制約

解法

まず rewarding でないエッジをすべて削除する．

次に DFS で B から逆辺を辿ることにより，ある頂点 v から B へ到達できるかどうかを調べる． A から到達できないときはこの時点で「VOID」と答えて終了．

最後に B へ到達できる頂点に関して，ベルマンフォードで A からの最短経路を求める． 負閉路があった場合は「UNBOUND」で，そうでないときはコストの合計と道程を答える．

  1 #include <iostream>
  2 #include <sstream>
  3 #include <vector>
  4 #include <algorithm>
  5 using namespace std;
  6 static const int INF = 10000000;
  7 
  8 struct edge
  9 {
 10   int u, v, cost, len;
 11   edge(int a, int b, int c, int d)
 12     : u(a), v(b), cost(c), len(d)
 13   {}
 14   bool operator<(const edge& e) const { return cost < e.cost; }
 15 };
 16 
 17 void dfs(int n, const vector<edge>& es, vector<int>& reachable)
 18 {
 19   reachable[n] = true;
 20   for (vector<edge>::const_iterator it = es.begin(); it != es.end(); ++it) {
 21     if (it->v == n && !reachable[it->u]) {
 22       dfs(it->u, es, reachable);
 23     }
 24   }
 25 }
 26 
 27 int main()
 28 {
 29   ios::sync_with_stdio(false);
 30   int N;
 31   while (cin >> N) {
 32     int M, A, B;
 33     cin >> M >> A >> B;
 34     vector<vector<edge> > g(N);
 35     vector<int> gm(N, INF);
 36     for (int i = 0; i < M; i++) {
 37       string s;
 38       cin >> s;
 39       stringstream ss;
 40       for (string::const_iterator it = s.begin(); it != s.end(); ++it) {
 41         switch (*it) {
 42           case '(':
 43           case ',':
 44           case '[':
 45           case ']':
 46           case ')':
 47             ss << ' ';  break;
 48           default:
 49             ss << *it;  break;
 50         }
 51       }
 52       int u, v, uv, l, vu;
 53       ss >> u >> v >> uv >> l >> vu;
 54       gm[u] = min(gm[u], uv);
 55       gm[v] = min(gm[v], vu);
 56       g[u].push_back(edge(u, v, uv, l));
 57       g[v].push_back(edge(v, u, vu, l));
 58     }
 59 
 60     vector<edge> es;
 61     for (int n = 0; n < N; n++) {
 62       if (!g[n].empty()) {
 63         for (vector<edge>::const_iterator it = g[n].begin(); it != g[n].end(); ++it) {
 64           if (it->cost == gm[n]) {
 65             es.push_back(*it);
 66           }
 67         }
 68       }
 69     }
 70 
 71     vector<int> reachable(N, false);
 72     dfs(B, es, reachable);
 73     if (!reachable[A]) {
 74       cout << "VOID" << endl;
 75       continue;
 76     }
 77 
 78     vector<int> cs(N, INF), ls(N, INF);
 79     cs[A] = ls[A] = 0;
 80     bool updated = true;
 81     for (int i = 0; updated && i <= N; i++) {
 82       updated = false;
 83       for (vector<edge>::const_iterator it = es.begin(); it != es.end(); ++it) {
 84         if (!reachable[it->v] || cs[it->u] == INF) {
 85           continue;
 86         }
 87         const int c = cs[it->u] + it->cost;
 88         const int l = ls[it->u] + it->len;
 89         if (c < cs[it->v] || (c == cs[it->v] && l < ls[it->v])) {
 90           cs[it->v] = c;
 91           ls[it->v] = ls[it->u] + it->len;
 92           updated = true;
 93         }
 94       }
 95     }
 96 
 97     if (updated) {
 98       cout << "UNBOUND" << endl;
 99     } else {
100       cout << cs[B] << ' ' << ls[B] << endl;
101     }
102   }
103   return 0;
104 }
poj/2679.cc