#include <iostream>
#include <vector>
#include <array>
#include <utility>
#include <queue>
#include <algorithm>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<array<int, 3>>> adj(n);
for (int i = 0; i < m; i++) {
int a, b, c, p;
cin >> a >> b >> c >> p;
a--; b--;
adj[a].push_back({ c, p, b });
adj[b].push_back({ c, p, a });
}
vector<vector<long long>> dp(n);
vector<vector<pair<int, long long>>> total(n);
for (int i = 0; i < n; i++) {
sort(adj[i].begin(), adj[i].end());
for (int j = 0; j < adj[i].size(); j++) {
if (j == 0 || total[i][total[i].size() - 1].first != adj[i][j][0])
total[i].push_back({ adj[i][j][0], 0 });
total[i][total[i].size() - 1].second += adj[i][j][1];
}
dp[i].resize(adj[i].size() + 1, 1e18);
}
priority_queue<pair<long long, array<int, 5>>> q;
q.push({ 0, { 0, 0, 0, 0, 0 } });
while (!q.empty()) {
auto [ nd, x ] = q.top();
// from v to u
auto [ t, c, p, u, v ] = x;
long long d = -nd;
q.pop();
if (dp[u][dp[u].size() - 1] > d) {
dp[u][dp[u].size() - 1] = d;
for (auto arr : adj[u]) {
long long tot = (*lower_bound(total[u].begin(), total[u].end(), make_pair(arr[0], -1LL))).second;
q.push({ -(d + tot - arr[1]), { 0, 0, 0, arr[2], u } });
q.push({ -(d + arr[1]), { 1, arr[0], arr[1], arr[2], u } });
}
}
if (t == 1) {
auto st = lower_bound(adj[u].begin(), adj[u].end(), array<int, 3>{ c, p, v });
int i = st - adj[u].begin();
if (dp[u][i] <= d) continue;
dp[u][i] = d;
auto it = lower_bound(adj[u].begin(), adj[u].end(), array<int, 3>{ c + 1, -1, 0 });
it--;
if (it == st) {
if (it == adj[u].begin()) continue;
else it--;
}
if ((*it)[0] != c) continue;
long long tot = (*lower_bound(total[u].begin(), total[u].end(), make_pair(c, -1LL))).second;
auto [ c2, p2, v2 ] = *it;
q.push({ -(d + tot - p - p2), { 0, 0, 0, v2, u } });
}
}
long long ans = 1e18;
for (auto e : dp[n - 1])
ans = min(ans, e);
if (ans == 1e18) cout << -1;
else cout << ans;
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:29:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for (int j = 0; j < adj[i].size(); j++) {
| ~~^~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
2 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
4 ms |
860 KB |
Output is correct |
10 |
Correct |
4 ms |
1016 KB |
Output is correct |
11 |
Correct |
4 ms |
988 KB |
Output is correct |
12 |
Correct |
3 ms |
860 KB |
Output is correct |
13 |
Correct |
4 ms |
984 KB |
Output is correct |
14 |
Correct |
4 ms |
984 KB |
Output is correct |
15 |
Correct |
2 ms |
604 KB |
Output is correct |
16 |
Correct |
3 ms |
604 KB |
Output is correct |
17 |
Correct |
3 ms |
860 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
5 ms |
860 KB |
Output is correct |
20 |
Correct |
2 ms |
604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
227 ms |
26628 KB |
Output is correct |
2 |
Correct |
88 ms |
10076 KB |
Output is correct |
3 |
Correct |
372 ms |
46648 KB |
Output is correct |
4 |
Correct |
129 ms |
17092 KB |
Output is correct |
5 |
Correct |
613 ms |
44920 KB |
Output is correct |
6 |
Correct |
556 ms |
45292 KB |
Output is correct |
7 |
Correct |
469 ms |
60832 KB |
Output is correct |
8 |
Correct |
427 ms |
27220 KB |
Output is correct |
9 |
Correct |
428 ms |
27728 KB |
Output is correct |
10 |
Correct |
287 ms |
35004 KB |
Output is correct |
11 |
Correct |
103 ms |
17696 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
2 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
4 ms |
860 KB |
Output is correct |
10 |
Correct |
4 ms |
1016 KB |
Output is correct |
11 |
Correct |
4 ms |
988 KB |
Output is correct |
12 |
Correct |
3 ms |
860 KB |
Output is correct |
13 |
Correct |
4 ms |
984 KB |
Output is correct |
14 |
Correct |
4 ms |
984 KB |
Output is correct |
15 |
Correct |
2 ms |
604 KB |
Output is correct |
16 |
Correct |
3 ms |
604 KB |
Output is correct |
17 |
Correct |
3 ms |
860 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
5 ms |
860 KB |
Output is correct |
20 |
Correct |
2 ms |
604 KB |
Output is correct |
21 |
Correct |
227 ms |
26628 KB |
Output is correct |
22 |
Correct |
88 ms |
10076 KB |
Output is correct |
23 |
Correct |
372 ms |
46648 KB |
Output is correct |
24 |
Correct |
129 ms |
17092 KB |
Output is correct |
25 |
Correct |
613 ms |
44920 KB |
Output is correct |
26 |
Correct |
556 ms |
45292 KB |
Output is correct |
27 |
Correct |
469 ms |
60832 KB |
Output is correct |
28 |
Correct |
427 ms |
27220 KB |
Output is correct |
29 |
Correct |
428 ms |
27728 KB |
Output is correct |
30 |
Correct |
287 ms |
35004 KB |
Output is correct |
31 |
Correct |
103 ms |
17696 KB |
Output is correct |
32 |
Correct |
403 ms |
45160 KB |
Output is correct |
33 |
Correct |
315 ms |
29912 KB |
Output is correct |
34 |
Correct |
450 ms |
34748 KB |
Output is correct |
35 |
Correct |
392 ms |
31964 KB |
Output is correct |
36 |
Correct |
352 ms |
38324 KB |
Output is correct |
37 |
Correct |
431 ms |
40244 KB |
Output is correct |
38 |
Correct |
471 ms |
60048 KB |
Output is correct |
39 |
Correct |
459 ms |
49796 KB |
Output is correct |
40 |
Correct |
368 ms |
28804 KB |
Output is correct |
41 |
Correct |
462 ms |
29172 KB |
Output is correct |
42 |
Correct |
485 ms |
43444 KB |
Output is correct |
43 |
Correct |
181 ms |
20672 KB |
Output is correct |
44 |
Correct |
625 ms |
51468 KB |
Output is correct |
45 |
Correct |
298 ms |
24796 KB |
Output is correct |
46 |
Correct |
245 ms |
23636 KB |
Output is correct |
47 |
Correct |
411 ms |
56264 KB |
Output is correct |
48 |
Correct |
651 ms |
63980 KB |
Output is correct |