## 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;
}
```