#include <bits/stdc++.h>
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
#define endl '\n'
#define ll long long
#define all(x) x.begin(), x.end()
struct Node {
ll to, color, cost;
};
unordered_map<int, vector<Node>> edg[100005];
unordered_map<int, ll> sum[100005], dp2[100005];
ll dp[100005];
int n, m;
struct T {
ll dist, place, color;
};
bool operator<(T a, T b) { return a.dist > b.dist; }
void solve() {
priority_queue<T> pq;
pq.push({0, 1, 0});
while (pq.size() > 0) {
T top = pq.top();
pq.pop();
if (top.color) {
if (top.dist != dp2[top.place][top.color]) continue;
for (auto [to, color, cost] : edg[top.place][top.color]) {
ll newCost = top.dist + sum[top.place][color] - cost;
if (newCost < dp[to]) {
dp[to] = newCost;
pq.push({dp[to], to, 0});
}
}
continue;
}
if (top.dist != dp[top.place]) continue;
for (auto x : edg[top.place]) {
for (auto [to, color, cost] : x.second) {
ll newCost = top.dist + min(cost, sum[top.place][color] - cost);
if (newCost < dp[to]) {
dp[to] = newCost;
pq.push({dp[to], to, 0});
}
if (!dp2[to].count(color) || top.dist < dp2[to][color]) {
dp2[to][color] = top.dist;
pq.push({dp2[to][color], to, color});
}
}
}
}
cout << ((dp[n] == LLONG_MAX) ? -1 : dp[n]);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for (int i = 2; i <= n; i++) dp[i] = LLONG_MAX;
for (int i = 0; i < m; i++) {
ll from, to, color, cost;
cin >> from >> to >> color >> cost;
edg[from][color].push_back({to, color, cost});
edg[to][color].push_back({from, color, cost});
sum[from][color] += cost;
sum[to][color] += cost;
}
solve();
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
16724 KB |
Output is correct |
2 |
Correct |
9 ms |
16724 KB |
Output is correct |
3 |
Correct |
9 ms |
16724 KB |
Output is correct |
4 |
Correct |
9 ms |
16724 KB |
Output is correct |
5 |
Correct |
9 ms |
16812 KB |
Output is correct |
6 |
Correct |
9 ms |
16724 KB |
Output is correct |
7 |
Correct |
10 ms |
16852 KB |
Output is correct |
8 |
Correct |
9 ms |
16840 KB |
Output is correct |
9 |
Correct |
11 ms |
17452 KB |
Output is correct |
10 |
Correct |
11 ms |
17492 KB |
Output is correct |
11 |
Correct |
13 ms |
17396 KB |
Output is correct |
12 |
Correct |
12 ms |
17364 KB |
Output is correct |
13 |
Correct |
11 ms |
17364 KB |
Output is correct |
14 |
Correct |
10 ms |
17364 KB |
Output is correct |
15 |
Correct |
10 ms |
17236 KB |
Output is correct |
16 |
Correct |
11 ms |
17352 KB |
Output is correct |
17 |
Correct |
11 ms |
17236 KB |
Output is correct |
18 |
Correct |
10 ms |
17000 KB |
Output is correct |
19 |
Correct |
10 ms |
16980 KB |
Output is correct |
20 |
Correct |
10 ms |
17236 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
167 ms |
38456 KB |
Output is correct |
2 |
Correct |
65 ms |
28464 KB |
Output is correct |
3 |
Correct |
157 ms |
36292 KB |
Output is correct |
4 |
Correct |
122 ms |
33936 KB |
Output is correct |
5 |
Correct |
684 ms |
98712 KB |
Output is correct |
6 |
Correct |
662 ms |
90348 KB |
Output is correct |
7 |
Correct |
377 ms |
79340 KB |
Output is correct |
8 |
Correct |
482 ms |
74936 KB |
Output is correct |
9 |
Correct |
513 ms |
74944 KB |
Output is correct |
10 |
Correct |
310 ms |
54820 KB |
Output is correct |
11 |
Correct |
147 ms |
46224 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
16724 KB |
Output is correct |
2 |
Correct |
9 ms |
16724 KB |
Output is correct |
3 |
Correct |
9 ms |
16724 KB |
Output is correct |
4 |
Correct |
9 ms |
16724 KB |
Output is correct |
5 |
Correct |
9 ms |
16812 KB |
Output is correct |
6 |
Correct |
9 ms |
16724 KB |
Output is correct |
7 |
Correct |
10 ms |
16852 KB |
Output is correct |
8 |
Correct |
9 ms |
16840 KB |
Output is correct |
9 |
Correct |
11 ms |
17452 KB |
Output is correct |
10 |
Correct |
11 ms |
17492 KB |
Output is correct |
11 |
Correct |
13 ms |
17396 KB |
Output is correct |
12 |
Correct |
12 ms |
17364 KB |
Output is correct |
13 |
Correct |
11 ms |
17364 KB |
Output is correct |
14 |
Correct |
10 ms |
17364 KB |
Output is correct |
15 |
Correct |
10 ms |
17236 KB |
Output is correct |
16 |
Correct |
11 ms |
17352 KB |
Output is correct |
17 |
Correct |
11 ms |
17236 KB |
Output is correct |
18 |
Correct |
10 ms |
17000 KB |
Output is correct |
19 |
Correct |
10 ms |
16980 KB |
Output is correct |
20 |
Correct |
10 ms |
17236 KB |
Output is correct |
21 |
Correct |
167 ms |
38456 KB |
Output is correct |
22 |
Correct |
65 ms |
28464 KB |
Output is correct |
23 |
Correct |
157 ms |
36292 KB |
Output is correct |
24 |
Correct |
122 ms |
33936 KB |
Output is correct |
25 |
Correct |
684 ms |
98712 KB |
Output is correct |
26 |
Correct |
662 ms |
90348 KB |
Output is correct |
27 |
Correct |
377 ms |
79340 KB |
Output is correct |
28 |
Correct |
482 ms |
74936 KB |
Output is correct |
29 |
Correct |
513 ms |
74944 KB |
Output is correct |
30 |
Correct |
310 ms |
54820 KB |
Output is correct |
31 |
Correct |
147 ms |
46224 KB |
Output is correct |
32 |
Correct |
107 ms |
31024 KB |
Output is correct |
33 |
Correct |
149 ms |
36440 KB |
Output is correct |
34 |
Correct |
399 ms |
54232 KB |
Output is correct |
35 |
Correct |
305 ms |
49028 KB |
Output is correct |
36 |
Correct |
342 ms |
71036 KB |
Output is correct |
37 |
Correct |
434 ms |
74612 KB |
Output is correct |
38 |
Correct |
384 ms |
84340 KB |
Output is correct |
39 |
Correct |
148 ms |
36208 KB |
Output is correct |
40 |
Correct |
510 ms |
74928 KB |
Output is correct |
41 |
Correct |
550 ms |
74968 KB |
Output is correct |
42 |
Correct |
534 ms |
74956 KB |
Output is correct |
43 |
Correct |
179 ms |
38124 KB |
Output is correct |
44 |
Correct |
276 ms |
41108 KB |
Output is correct |
45 |
Correct |
376 ms |
71372 KB |
Output is correct |
46 |
Correct |
333 ms |
70780 KB |
Output is correct |
47 |
Correct |
378 ms |
73488 KB |
Output is correct |
48 |
Correct |
696 ms |
99264 KB |
Output is correct |