2013年9月3日

UVa 1112 - Mice and Maze

WA for 7 times just beacuse I always use T as variable of case number.
#include <cstdio>
#include <vector>
#include <queue>
#define PB push_back
using namespace std;

struct State {
  State(int now, int need) : now(now), need(need) {}
  bool operator<(const State & other) const {
    return need > other.need;
  }
  int now, need;
};

int main() {
  int Case;
  scanf("%d", &Case);
  while (Case--) {
    int N, E, T, M, need[101][101];
    vector<int> con[101];
    scanf("%d%d%d%d", &N, &E, &T, &M);
    while (M--) {
      int a, b, t;
      scanf("%d%d%d", &a, &b, &t);
      con[b].PB(a);
      need[b][a] = t;
    }
    int best[101];
    for (int i = 1; i <= N; i++) {
      best[i] = 1e8;
    }
    best[E] = 0;
    priority_queue<State> pq;
    pq.push(State(E, 0));
    while (!pq.empty()) {
      int now = pq.top().now, use = pq.top().need;
      pq.pop();
      if (use > T) {
        break;
      }
      for (int i = 0; i < con[now].size(); i++) {
        int j = con[now][i];
        if (use + need[now][j] < best[j]) {
          best[j] = use + need[now][j];
          pq.push(State(j, best[j]));
        }
      }
    }
    int ans = 0;
    for (int i = 1; i <= N; i++) {
      ans += (best[i] <= T);
    }
    printf("%d\n", ans);
    if (Case) {
      puts("");
    }
  }
  return 0;
}

沒有留言:

張貼留言