QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#532718 | #5081. Forbidden Turns | BongoCatEnjoyer# | TL | 134ms | 19008kb | C++14 | 1.9kb | 2024-08-25 10:09:53 | 2024-08-25 10:09:54 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define forn(i, n) for (ll i = 0; i < n; ++i)
#define forr(i, s, n) for (ll i = s; i < n; ++i)
#define fori(i, s, n) for (ll i = s; i > n; --i)
#define fora(i, n) for (auto i: n)
#define vi vector<int>
#define vll vector<ll>
#define prints(n) cout << (n) << " "
#define println(n) cout << (n) << "\n"
const int MOD = 998244353;
// const int MOD = 1e9 + 7;
void solve() {
ll m, n, k; cin >> m >> n >> k;
ll s, t; cin >> s >> t;
vector<vector<pair<ll, ll>>> adj(n, vector<pair<ll, ll>>());
map<pair<ll, ll>, ll> mp;
forn(i, m) {
ll u, v, w; cin >> u >> v >> w;
adj[u].push_back({v, w});
mp[{u, v}] = i;
}
vector<set<pair<ll, ll>>> st(n, set<pair<ll, ll>>());
forn(i, k) {
ll a, b, c; cin >> a >> b >> c;
st[b].insert({a, c});
}
// Tuple -Dist, Curr, Prev
priority_queue<tuple<ll, ll, ll>> pq;
pq.push({0, s, -1});
ll ans = -1;
vector<bool> visn(n), vise(m);
while (!pq.empty()) {
auto [dist, curr, prev] = pq.top(); pq.pop();
// prints(dist); prints(curr); println(prev);
if (curr == t) {
ans = -dist; break;
}
if (visn[curr]) continue;
visn[curr] = true;
fora(edge, adj[curr]) {
ll next = edge.first, cost = edge.second;
if (visn[next]) continue;
if (vise[mp[{curr, next}]]) continue;
if (st[curr].find({prev, next}) != st[curr].end()) {
visn[curr] = false; continue;
}
pq.push({dist - cost, next, curr});
}
}
println(ans);
}
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3664kb
input:
9 7 3 3 2 6 3 2 3 0 3 0 1 12 1 0 4 1 2 2 1 5 4 4 1 8 5 4 7 5 2 5 0 1 2 4 1 5 1 5 2
output:
36
result:
ok single line: '36'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3504kb
input:
4 4 1 0 3 0 1 2 1 2 3 0 2 7 2 3 10 0 1 2
output:
17
result:
ok single line: '17'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3500kb
input:
4 4 0 0 3 0 1 2 1 2 3 0 2 7 2 3 10
output:
15
result:
ok single line: '15'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
4 4 1 1 0 1 2 3 2 3 10 3 2 12 2 0 7 1 2 0
output:
32
result:
ok single line: '32'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
13 8 5 0 5 0 2 3 2 1 7 4 2 10 2 3 10 3 2 12 2 5 10 3 6 10 6 7 5 7 3 5 6 4 10 4 1 0 1 4 10 4 6 10 0 2 1 0 2 5 3 2 5 2 3 2 6 4 2
output:
63
result:
ok single line: '63'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
4 4 2 1 0 1 2 3 2 3 10 3 2 12 2 0 7 1 2 0 2 3 2
output:
-1
result:
ok single line: '-1'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
4 4 0 1 0 1 2 3 2 3 2 3 2 3 2 0 7
output:
10
result:
ok single line: '10'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
0 1 0 0 0
output:
0
result:
ok single line: '0'
Test #9:
score: 0
Accepted
time: 29ms
memory: 12268kb
input:
59996 30000 29997 0 29999 0 1 3 1 29999 7 1 2 1 2 1 1 2 3 1 3 2 1 3 4 1 4 3 1 4 5 1 5 4 1 5 6 1 6 5 1 6 7 1 7 6 1 7 8 1 8 7 1 8 9 1 9 8 1 9 10 1 10 9 1 10 11 1 11 10 1 11 12 1 12 11 1 12 13 1 13 12 1 13 14 1 14 13 1 14 15 1 15 14 1 15 16 1 16 15 1 16 17 1 17 16 1 17 18 1 18 17 1 18 19 1 19 18 1 19 2...
output:
60004
result:
ok single line: '60004'
Test #10:
score: 0
Accepted
time: 97ms
memory: 18240kb
input:
54776 10000 149059 0 9999 0 1168 720 0 7849 347 0 5301 937 0 1176 113 0 4762 833 0 6595 630 0 5846 548 0 528 878 1 3794 680 1 5036 171 1 4938 977 1 3180 522 1 9790 3 1 2139 221 1 3003 470 2 1054 534 2 5405 899 2 8279 740 2 1749 864 2 4634 773 2 7027 960 2 8151 321 2 4893 201 3 960 939 4 2349 671 5 6...
output:
2041
result:
ok single line: '2041'
Test #11:
score: 0
Accepted
time: 83ms
memory: 18412kb
input:
54727 10000 149795 0 9999 0 2611 51 0 6360 105 0 9596 66 0 7534 845 0 8007 758 0 1455 356 1 5761 949 1 5075 518 1 9029 436 1 432 235 1 4260 356 1 2845 870 1 5620 793 1 8169 483 2 4993 131 2 5942 50 2 3295 965 2 8977 538 3 8231 754 3 3852 321 3 3800 424 3 1731 493 4 5578 42 4 4697 337 4 3900 54 4 444...
output:
2572
result:
ok single line: '2572'
Test #12:
score: 0
Accepted
time: 134ms
memory: 19008kb
input:
55101 10000 151145 0 9999 0 8800 169 0 1752 969 1 6634 310 1 3693 284 1 1650 910 1 5991 323 1 2499 279 1 5189 154 1 4153 425 2 5566 738 2 2769 947 3 7442 71 3 4856 367 3 1109 398 3 6801 846 4 8109 118 4 290 414 4 315 259 4 4814 323 4 4821 135 5 2971 275 5 8576 605 6 7061 788 6 6608 336 6 1414 671 6 ...
output:
4445
result:
ok single line: '4445'
Test #13:
score: 0
Accepted
time: 113ms
memory: 18964kb
input:
54756 10000 150207 0 9999 0 1148 773 0 5763 985 0 2835 602 0 977 30 0 9223 600 0 2104 51 0 2094 617 1 4084 55 1 8160 512 1 2837 284 2 3303 473 2 9720 598 2 3700 191 2 9804 546 2 5114 882 2 7947 903 2 4817 499 3 5985 705 3 709 686 3 7579 496 3 172 434 3 7311 760 3 4812 52 4 609 174 5 1269 115 5 4314 ...
output:
3096
result:
ok single line: '3096'
Test #14:
score: 0
Accepted
time: 119ms
memory: 18760kb
input:
54656 10000 150741 0 9999 0 1511 252 0 7148 940 0 486 614 0 4770 773 0 2790 17 0 3626 76 0 9832 174 0 4562 827 1 5855 35 1 9290 513 1 2982 35 1 2854 751 1 6897 316 2 4990 733 2 5224 761 2 3283 21 3 6955 163 3 4823 213 3 2286 385 3 4033 965 4 9836 810 4 9699 309 5 1609 184 5 4014 366 6 6616 824 6 430...
output:
2876
result:
ok single line: '2876'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
6 5 1 1 0 1 2 3 2 3 10 3 2 12 2 0 7 3 4 20 4 0 30 1 2 0
output:
32
result:
ok single line: '32'
Test #16:
score: -100
Time Limit Exceeded
input:
54620 10000 148088 0 9999 0 8788 329 0 5514 152 0 8678 225 0 373 846 0 3314 720 0 8746 235 0 7183 822 0 6125 619 1 8172 190 2 4792 153 2 1637 513 2 8863 382 2 5682 160 2 1245 423 3 2635 430 3 7675 950 3 1297 203 3 7691 368 3 2102 619 3 4561 911 4 9702 137 4 3518 713 4 3199 10 5 6043 169 5 5485 427 5...