UVA1112

Posted on | In ,

Mice and Maze

Solution sketch

裸的 最短路徑 題。

注意邊要反著建立，畢竟你的終點變起點了……

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 111;
const int MAX = 0x3f3f3f3f;
typedef pair<int, int> ii;
struct Edge {
    int to, cost;
    Edge(int a, int b)
    {
        to = a;
        cost = b;
    }
};
vector<Edge> g[MAX_N];
int n, e, t, m;
int dist[MAX_N];
void dijkstra(int s)
{
    memset(dist, 0x3f, sizeof(dist));
    dist[s] = 0;
    priority_queue<ii, vector<ii>, greater<ii>> pq;
    pq.push(ii(0, s));
    while (pq.size() > 0) {
        ii cur = pq.top();
        pq.pop();
        int v = cur.second;
        int d = cur.first;
        if (dist[v] < d)
            continue;
        for (auto edge : g[v]) {
            int newDist = d + edge.cost;
            if (dist[edge.to] > newDist) {
                dist[edge.to] = newDist;
                pq.push(ii(dist[edge.to], edge.to));
            }
        }
    }
}
void solve()
{
    scanf("%d %d %d %d", &n, &e, &t, &m);
    for (int i = 0; i < n; i++)
        g[i].clear();
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        u--;
        v--;
        g[v].push_back(Edge(u, w)); // notice...
    }
    dijkstra(e - 1);
    int ans = 0;
    for (int i = 0; i < n; i++)
        if (dist[i] <= t)
            ans++;
    printf("%d\n", ans);
}
int main()
{
    int ncase;
    scanf("%d", &ncase);
    while (ncase--) {
        solve();
        if (ncase)
            printf("\n");
    }
    return 0;
}