2012年11月22日

UVa 10986 - Sending email


#include <cstdio>
#include <queue>
#include <map>
#include <vector>
#define MP make_pair
using namespace std;

typedef pair<int, int> P;

int main() {
  int i, j, k, C, N;
  scanf("%d", &N);
  for (C = 1; C <= N; C++) {
    int n, m, S, T;
    scanf("%d%d%d%d", &n, &m, &S, &T);
    map<P, int> dis;
    vector<int> v[20005];
    for (i = 0; i < m; i++) {
      int a, b, w;
      scanf("%d%d%d", &a, &b, &w);
      dis[MP(a, b)] = dis[MP(b, a)] = w;
      v[a].push_back(b);
      v[b].push_back(a);
    }
    int d[20005];
    for (i = 0; i < n; i++)
      d[i] = 2e9;
    d[S] = 0;
    queue<int> q;
    q.push(S);
    while (!q.empty()) {
      int a = q.front(), b;
      q.pop();
      for (i = 0; i < v[a].size(); i++) {
        b = v[a][i];
        if (dis.count(MP(a, b))) {
          int w = dis[MP(a, b)];
          if (d[a] + w < d[b]) {
            d[b] = d[a] + w;
            q.push(b);
          }
        }
      }
    }
    printf("Case #%d: ", C);
    if (d[T] != 2e9) printf("%d\n", d[T]);
    else puts("unreachable");
  }
  return 0;
}

沒有留言:

張貼留言