2013年3月12日

UVa 341 - Non-Stop Travel


#include <stdio.h>
#include <string.h>

void path(int* prev, int now) {
  if (prev[now] != now) path(prev, prev[now]);
  printf(" %d", now);
}

int main() {
  int n, C = 1;
  while (scanf("%d", &n) && n) {
    int i, j, k, d, len[100][100];
    memset(len, -1, sizeof(len));
    for (i = 1; i <= n; i++) {
      scanf("%d", &k);
      while (k--) {
        scanf("%d%d", &j, &d);
        len[i][j] = d;
      }
    }
    int start, end;
    scanf("%d%d", &start, &end);
    int dis[100], prev[100], v[100] = {};
    memset(prev, -1, sizeof(prev));
    for (i = 1; i <= n; i++)
      dis[i] = 2e9;
    dis[start] = 0;
    prev[start] = start;
    while (1) {
      int now = -1, min = 2e9;
      for (i = 1; i <= n; i++)
        if (!v[i] && dis[i] < min) min = dis[i], now = i;
      if (now == -1) break;
      v[now] = 1;
      for (i = 1; i <= n; i++)
        if (!v[i] && len[now][i] != -1 && dis[now] + len[now][i] < dis[i]) dis[i] = dis[now] + len[now][i], prev[i] = now;
    }
    printf("Case %d: Path =", C++);
    path(prev, end);
    printf("; %d second delay\n", dis[end]);
  }
  return 0;
}

沒有留言:

張貼留言