POJ 3767 - I Wanna Go Home

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

概要

N 個の街を M 本の道が繋いでおり，i 番目の道を通って行くには T[i] の時間がかかる． 道を通って双方向に移動できる．

各街は指導者1か指導者2のいずれかを支持している． 支持している指導者が異なる街の間の移動は多くとも1回にしたい．

街1から街2まで行くのに最短でどれくらい時間がかかるかを答える． ただし，条件を守るように行けない場合は -1 を答える．

街1は指導者1を支持しており，街2は指導者2を支持している．

制約

解法

指導者2を支持している街から指導者1を支持している街へは移動できないので，この方向のエッジを除いた有向グラフ上で普通にダイクストラで最短経路を求めればいい．

 1 #include <cstdio>
 2 #include <vector>
 3 #include <queue>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 struct edge { int u, v, c; };
 8 
 9 int main()
10 {
11   int N;
12   while (scanf("%d", &N) != EOF && N != 0) {
13     int M;
14     scanf("%d", &M);
15     static vector<pair<int,int> > g[600];
16     for (int i = 0; i < N; i++) {
17       g[i].clear();
18     }
19 
20     static edge es[10000];
21     for (int i = 0; i < M; i++) {
22       scanf("%d %d %d", &es[i].u, &es[i].v, &es[i].c);
23       --es[i].v;  --es[i].u;
24     }
25     static int color[600];
26     for (int i = 0; i < N; i++) {
27       scanf("%d", &color[i]);
28     }
29     for (int i = 0; i < M; i++) {
30       if (color[es[i].u] <= color[es[i].v]) {
31         g[es[i].u].push_back(make_pair(es[i].v, es[i].c));
32       }
33       if (color[es[i].v] <= color[es[i].u]) {
34         g[es[i].v].push_back(make_pair(es[i].u, es[i].c));
35       }
36     }
37 
38     static int dist[600];
39     static const int INF = 10000000;
40     fill_n(dist, N, INF);
41     priority_queue<pair<int,int> > q;
42     q.push(make_pair(0, 0));
43     dist[0] = 0;
44     while (!q.empty()) {
45       const int c = -q.top().first;
46       const int n = q.top().second;
47       q.pop();
48       if (n == 1) {
49         break;
50       }
51       if (dist[n] < c) {
52         continue;
53       }
54       for (vector<pair<int,int> >::const_iterator it = g[n].begin(); it != g[n].end(); ++it) {
55         const int m = it->first;
56         const int cc = c + it->second;
57         if (cc < dist[m]) {
58           dist[m] = cc;
59           q.push(make_pair(-cc, m));
60         }
61       }
62     }
63     if (dist[1] == INF) {
64       puts("-1");
65     } else {
66       printf("%d\n", dist[1]);
67     }
68   }
69   return 0;
70 }
poj/3767.cc