-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathaceptaelreto 601 - AC.cpp
63 lines (50 loc) · 1.25 KB
/
aceptaelreto 601 - AC.cpp
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
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef pair <int, int> ii;
typedef vector<int> vi;
typedef vector<vector<ii>> vvii;
#define FOR(a, b, i) for (int i = a; i<b; ++i)
#define INF 10000000
int V, s, T, E;
vvii AdjList;
// Dijkstra, O((V+E)logV)
int dijkstra() {
vi dist(V, INF); dist[s] = 0;
priority_queue< ii, vector<ii>, greater<ii> > pq; // functional
pq.push(ii(0, s));
while (!pq.empty()) {
ii front = pq.top(); pq.pop();
int d = front.first, u = front.second;
if (d > dist[u]) continue; // important check
for (int j = 0; j < (int)AdjList[u].size(); j++) {
ii v = AdjList[u][j]; //Adjlist: (node, weight)
if (dist[u] + v.second < dist[v.first]) {
dist[v.first] = dist[u] + v.second;
pq.push(ii(dist[v.first], v.first));
}
}
}
int sol = 0;
FOR(0, V, i) {
if (dist[i] <= T)++sol;
}
return sol;
}
int main() {
while (cin >> V) {
cin >> s; cin >> T; cin >> E;
--s;
AdjList.clear();
AdjList.resize(V);
int a, b, x;
while (E--) {
cin >> a; cin >> b; cin >> x;
//change E direction when filling the AdjList
AdjList[b - 1].push_back({ a - 1, x });
}
cout << dijkstra() - 1 << "\n";
}
return 0;
}