#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 300010, K = 4;
const ll inf = 1ll << 59;
unordered_map<int, vector<pair<int,int>>> edge[MAX_N];
int n, m;
ll dp[MAX_N], sec[MAX_N], fr[MAX_N], sef[MAX_N];
unordered_map<int, ll> mcdp[MAX_N];
struct info {
ll cur, len, col, lst, mc;
bool operator < (info b) const {
return len > b.len;
}
};
int32_t main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> n >> m;
for (int a, b, c, p, i = 0;i < m;++i) {
cin >> a >> b >> c >> p;
edge[a][c].pb(b, p);
edge[b][c].pb(a, p);
}
for (int i = 1;i <= n;++i) {
dp[i] = sec[i] = inf;
fr[i] = sef[i] = -1;
}
priority_queue<info> pq;
pq.push({1, 0, -1, -1, -1});
dp[1] = sec[1] = 0;
auto update = [&](int x, ll len, ll col, ll mc) {
if (mc == -1) {
bool ok = false;
if (len < dp[x]) {
swap(len, dp[x]);
swap(col, fr[x]);
ok = true;
}
if (len < sec[x] && fr[x] != col) {
swap(len, sec[x]);
swap(col, sef[x]);
ok = true;
}
return ok;
}
else {
if (!edge[x].count(mc)) return false;
if (mcdp[x].count(mc))
return chmin(mcdp[x][mc], len);
else return mcdp[x][mc] = len, true;
}
};
while (pq.size()) {
auto [x, len, col, lst, mc] = pq.top(); pq.pop();
DE(x, len, col);
if (mc == -1) {
if (len > sec[x]) continue;
for (auto [c, vec] : edge[x]) {
ll sum = 0;
for (auto [u, cost] : vec) {
if (u == lst && c != col) continue;
sum += cost;
}
for (auto [u, cost] : vec) {
if (u == lst) continue;
ll need = sum - cost;
if (c == col) need = inf;
if (update(u, need + len, c, -1))
pq.push({u, need + len, c, x, -1});
if (update(u, cost + len, -1, -1))
pq.push({u, cost + len, -1, x, -1});
if (update(u, len, -1, c))
pq.push({u, len, -1, x, c});
}
}
}
else {
if (len > mcdp[x][mc]) continue;
auto vec = edge[x][mc];
int c = mc;
ll sum = 0;
for (auto [u, cost] : vec)
sum += cost;
for (auto [u, cost] : vec) {
if (u == lst) continue;
ll need = sum - cost;
if (update(u, need + len, c, -1))
pq.push({u, need + len, c, x, -1});
}
}
}
if (dp[n] == inf) dp[n] = -1;
cout << dp[n] << '\n';
}
Compilation message
Main.cpp: In function 'int32_t main()':
Main.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
Main.cpp:81:3: note: in expansion of macro 'DE'
81 | DE(x, len, col);
| ^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
33260 KB |
Output is correct |
2 |
Correct |
23 ms |
33388 KB |
Output is correct |
3 |
Correct |
23 ms |
33280 KB |
Output is correct |
4 |
Correct |
23 ms |
33260 KB |
Output is correct |
5 |
Correct |
23 ms |
33260 KB |
Output is correct |
6 |
Correct |
24 ms |
33260 KB |
Output is correct |
7 |
Correct |
24 ms |
33388 KB |
Output is correct |
8 |
Correct |
24 ms |
33260 KB |
Output is correct |
9 |
Correct |
26 ms |
33644 KB |
Output is correct |
10 |
Correct |
27 ms |
33644 KB |
Output is correct |
11 |
Correct |
25 ms |
33644 KB |
Output is correct |
12 |
Correct |
25 ms |
33516 KB |
Output is correct |
13 |
Correct |
25 ms |
33644 KB |
Output is correct |
14 |
Correct |
25 ms |
33644 KB |
Output is correct |
15 |
Correct |
26 ms |
33388 KB |
Output is correct |
16 |
Correct |
26 ms |
33516 KB |
Output is correct |
17 |
Correct |
29 ms |
33516 KB |
Output is correct |
18 |
Correct |
24 ms |
33516 KB |
Output is correct |
19 |
Correct |
25 ms |
33388 KB |
Output is correct |
20 |
Correct |
25 ms |
33516 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
299 ms |
46176 KB |
Output is correct |
2 |
Correct |
125 ms |
40320 KB |
Output is correct |
3 |
Correct |
365 ms |
45740 KB |
Output is correct |
4 |
Correct |
173 ms |
42464 KB |
Output is correct |
5 |
Correct |
813 ms |
77376 KB |
Output is correct |
6 |
Correct |
742 ms |
75560 KB |
Output is correct |
7 |
Correct |
540 ms |
75776 KB |
Output is correct |
8 |
Correct |
418 ms |
56172 KB |
Output is correct |
9 |
Correct |
493 ms |
56188 KB |
Output is correct |
10 |
Correct |
476 ms |
54620 KB |
Output is correct |
11 |
Correct |
135 ms |
45036 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
33260 KB |
Output is correct |
2 |
Correct |
23 ms |
33388 KB |
Output is correct |
3 |
Correct |
23 ms |
33280 KB |
Output is correct |
4 |
Correct |
23 ms |
33260 KB |
Output is correct |
5 |
Correct |
23 ms |
33260 KB |
Output is correct |
6 |
Correct |
24 ms |
33260 KB |
Output is correct |
7 |
Correct |
24 ms |
33388 KB |
Output is correct |
8 |
Correct |
24 ms |
33260 KB |
Output is correct |
9 |
Correct |
26 ms |
33644 KB |
Output is correct |
10 |
Correct |
27 ms |
33644 KB |
Output is correct |
11 |
Correct |
25 ms |
33644 KB |
Output is correct |
12 |
Correct |
25 ms |
33516 KB |
Output is correct |
13 |
Correct |
25 ms |
33644 KB |
Output is correct |
14 |
Correct |
25 ms |
33644 KB |
Output is correct |
15 |
Correct |
26 ms |
33388 KB |
Output is correct |
16 |
Correct |
26 ms |
33516 KB |
Output is correct |
17 |
Correct |
29 ms |
33516 KB |
Output is correct |
18 |
Correct |
24 ms |
33516 KB |
Output is correct |
19 |
Correct |
25 ms |
33388 KB |
Output is correct |
20 |
Correct |
25 ms |
33516 KB |
Output is correct |
21 |
Correct |
299 ms |
46176 KB |
Output is correct |
22 |
Correct |
125 ms |
40320 KB |
Output is correct |
23 |
Correct |
365 ms |
45740 KB |
Output is correct |
24 |
Correct |
173 ms |
42464 KB |
Output is correct |
25 |
Correct |
813 ms |
77376 KB |
Output is correct |
26 |
Correct |
742 ms |
75560 KB |
Output is correct |
27 |
Correct |
540 ms |
75776 KB |
Output is correct |
28 |
Correct |
418 ms |
56172 KB |
Output is correct |
29 |
Correct |
493 ms |
56188 KB |
Output is correct |
30 |
Correct |
476 ms |
54620 KB |
Output is correct |
31 |
Correct |
135 ms |
45036 KB |
Output is correct |
32 |
Correct |
322 ms |
39968 KB |
Output is correct |
33 |
Correct |
378 ms |
44380 KB |
Output is correct |
34 |
Correct |
752 ms |
59736 KB |
Output is correct |
35 |
Correct |
558 ms |
51748 KB |
Output is correct |
36 |
Correct |
445 ms |
59228 KB |
Output is correct |
37 |
Correct |
513 ms |
62268 KB |
Output is correct |
38 |
Correct |
538 ms |
75300 KB |
Output is correct |
39 |
Correct |
308 ms |
42208 KB |
Output is correct |
40 |
Correct |
501 ms |
56192 KB |
Output is correct |
41 |
Correct |
542 ms |
56300 KB |
Output is correct |
42 |
Correct |
770 ms |
66448 KB |
Output is correct |
43 |
Correct |
313 ms |
46300 KB |
Output is correct |
44 |
Correct |
693 ms |
49248 KB |
Output is correct |
45 |
Correct |
402 ms |
55148 KB |
Output is correct |
46 |
Correct |
330 ms |
54636 KB |
Output is correct |
47 |
Correct |
536 ms |
62964 KB |
Output is correct |
48 |
Correct |
1040 ms |
80848 KB |
Output is correct |