2013年8月3日

UVa 318 - Domino Effect

#include <cstdio>
#include <vector>

int main() {
  int n, m, T = 1;
  while (scanf("%d%d", &n, &m) && n) {
    std::vector<int> con[501];
    int len[501][501];
    while (m--) {
      int a, b, t;
      scanf("%d%d%d", &a, &b, &t);
      len[a][b] = len[b][a] = t;
      con[a].push_back(b);
      con[b].push_back(a);
    }
    int dis[501] = {2e9, 0};
    bool vis[501] = {};
    for (int i = 2; i <= n; i++) {
      dis[i] = 2e9;
    }
    while (1) {
      int a = -1, min = 2e9;
      for (int i = 1; i <= n; i++) {
        if (!vis[i] && dis[i] < min) {
          min = dis[i];
          a = i;
        }
      }
      if (a == -1) {
        break;
      }
      vis[a] = true;
      for (int i = 0; i < con[a].size(); i++) {
        int b = con[a][i];
        if (dis[b] > dis[a] + len[a][b]) {
          dis[b] = dis[a] + len[a][b];
        }
      }
    }
    printf("System #%d\n", T++);
    int l = 1, r = -1;
    double max = 0;
    for (int a = 1; a <= n; a++) {
      if (dis[a] != 2e9 && dis[a] > max) {
        max = dis[a];
        l = a;
        r = -1;
      }
    }
    for (int a = 1; a <= n; a++) {
      for (int i = 0; i < con[a].size(); i++) {
        int b = con[a][i];
        int t1 = dis[a], t2 = dis[b];
        if (t1 < t2) {
          std::swap(t1, t2);
        }
        float endTime = t1 + (len[a][b] - (t1 - t2)) / 2.0;
        if (t1 != 2e9 && t2 != 2e9 && endTime > max) {
          l = a < b ? a : b;
          r = a > b ? a : b;
          max = endTime;
        }
      }
    }
    if (r == -1) {
      printf("The last domino falls after %.1lf seconds, at key domino %d.", max, l);
    } else {
      printf("The last domino falls after %.1lf seconds, between key dominoes %d and %d.", max, l, r);
    }
    puts("\n");
  }
  return 0;
}

沒有留言:

張貼留言