#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int MAXN = 1E5 + 5;
const i64 INF = 1E15;
i64 ncost;
i64 dp1[MAXN];
map <int, i64> sum[MAXN], dp2[MAXN];
map <int, vector <pair <int, int>>> adj[MAXN];
#define ONLINE_JUDGE
void solve() {
fill(dp1, dp1 + MAXN, INF);
int n, m;
cin >> n >> m;
for(int i = 1; i <= m; i++) {
int u, v, c, p;
cin >> u >> v >> c >> p;
adj[u][c].emplace_back(v, p);
adj[v][c].emplace_back(u, p);
sum[u][c] += p;
sum[v][c] += p;
}
using T = tuple <i64, int, int>;
priority_queue <T, vector <T>, greater <T>> pq; // [cost, ok, node]
pq.emplace(dp1[1] = 0, -1, 1);
while(!pq.empty()) {
auto [cost, ok, node] = pq.top();
pq.pop();
if(ok == -1) {
if(cost != dp1[node]) {
continue;
}
for(auto &[color, vec] : adj[node]) {
for(auto &[child, add] : vec) {
// Case 1: Flip neighbours
// Case 2: Flip yourself but don't your child's neighbours
ncost = cost + min(i64(add), sum[node][color] - add);
if(ncost < dp1[child]) {
//cerr << node << " " << cost << " -> " << child << " " << ncost << "\n";
pq.emplace(dp1[child] = ncost, -1, child);
}
// Case 3: Flip yourself and your child's neighbours
if(dp2[child].count(color) == 0 || cost < dp2[child][color]) {
//cerr << "go: " << node << " " << child << " :: " << color << " :: " << cost << "\n";
pq.emplace(dp2[child][color] = cost, color, child);
}
}
}
} else {
if(cost != dp2[node][ok]) {
continue;
}
// Only Case 1: Flip neighbours (including before)
for(auto &[child, add] : adj[node][ok]) {
ncost = cost + (sum[node][ok] - add);
if(ncost < dp1[child]) {
//cerr << "ex: " << node << " " << ok << " " << cost << " -> " << child << " " << ncost << "\n";
pq.emplace(dp1[child] = ncost, -1, child);
}
}
}
}
cout << (dp1[n] == INF ? -1 : dp1[n]);
return;
}
signed main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int t = 1; //cin >> t;
for(int i = 1; i <= t; i++) {
solve();
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
15196 KB |
Output is correct |
2 |
Correct |
3 ms |
15196 KB |
Output is correct |
3 |
Correct |
4 ms |
15196 KB |
Output is correct |
4 |
Correct |
3 ms |
15192 KB |
Output is correct |
5 |
Correct |
3 ms |
15196 KB |
Output is correct |
6 |
Correct |
3 ms |
15196 KB |
Output is correct |
7 |
Correct |
4 ms |
15448 KB |
Output is correct |
8 |
Correct |
4 ms |
15192 KB |
Output is correct |
9 |
Correct |
5 ms |
15704 KB |
Output is correct |
10 |
Correct |
5 ms |
15708 KB |
Output is correct |
11 |
Correct |
4 ms |
15552 KB |
Output is correct |
12 |
Correct |
4 ms |
15540 KB |
Output is correct |
13 |
Correct |
6 ms |
15448 KB |
Output is correct |
14 |
Correct |
4 ms |
15552 KB |
Output is correct |
15 |
Correct |
4 ms |
15452 KB |
Output is correct |
16 |
Correct |
6 ms |
15452 KB |
Output is correct |
17 |
Correct |
4 ms |
15452 KB |
Output is correct |
18 |
Correct |
4 ms |
15448 KB |
Output is correct |
19 |
Correct |
4 ms |
15452 KB |
Output is correct |
20 |
Correct |
4 ms |
15452 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
109 ms |
32196 KB |
Output is correct |
2 |
Correct |
53 ms |
24500 KB |
Output is correct |
3 |
Correct |
118 ms |
26836 KB |
Output is correct |
4 |
Correct |
64 ms |
26520 KB |
Output is correct |
5 |
Correct |
735 ms |
76372 KB |
Output is correct |
6 |
Correct |
584 ms |
71080 KB |
Output is correct |
7 |
Correct |
229 ms |
48180 KB |
Output is correct |
8 |
Correct |
276 ms |
46496 KB |
Output is correct |
9 |
Correct |
257 ms |
46740 KB |
Output is correct |
10 |
Correct |
231 ms |
46780 KB |
Output is correct |
11 |
Correct |
81 ms |
31056 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
15196 KB |
Output is correct |
2 |
Correct |
3 ms |
15196 KB |
Output is correct |
3 |
Correct |
4 ms |
15196 KB |
Output is correct |
4 |
Correct |
3 ms |
15192 KB |
Output is correct |
5 |
Correct |
3 ms |
15196 KB |
Output is correct |
6 |
Correct |
3 ms |
15196 KB |
Output is correct |
7 |
Correct |
4 ms |
15448 KB |
Output is correct |
8 |
Correct |
4 ms |
15192 KB |
Output is correct |
9 |
Correct |
5 ms |
15704 KB |
Output is correct |
10 |
Correct |
5 ms |
15708 KB |
Output is correct |
11 |
Correct |
4 ms |
15552 KB |
Output is correct |
12 |
Correct |
4 ms |
15540 KB |
Output is correct |
13 |
Correct |
6 ms |
15448 KB |
Output is correct |
14 |
Correct |
4 ms |
15552 KB |
Output is correct |
15 |
Correct |
4 ms |
15452 KB |
Output is correct |
16 |
Correct |
6 ms |
15452 KB |
Output is correct |
17 |
Correct |
4 ms |
15452 KB |
Output is correct |
18 |
Correct |
4 ms |
15448 KB |
Output is correct |
19 |
Correct |
4 ms |
15452 KB |
Output is correct |
20 |
Correct |
4 ms |
15452 KB |
Output is correct |
21 |
Correct |
109 ms |
32196 KB |
Output is correct |
22 |
Correct |
53 ms |
24500 KB |
Output is correct |
23 |
Correct |
118 ms |
26836 KB |
Output is correct |
24 |
Correct |
64 ms |
26520 KB |
Output is correct |
25 |
Correct |
735 ms |
76372 KB |
Output is correct |
26 |
Correct |
584 ms |
71080 KB |
Output is correct |
27 |
Correct |
229 ms |
48180 KB |
Output is correct |
28 |
Correct |
276 ms |
46496 KB |
Output is correct |
29 |
Correct |
257 ms |
46740 KB |
Output is correct |
30 |
Correct |
231 ms |
46780 KB |
Output is correct |
31 |
Correct |
81 ms |
31056 KB |
Output is correct |
32 |
Correct |
78 ms |
25292 KB |
Output is correct |
33 |
Correct |
78 ms |
27596 KB |
Output is correct |
34 |
Correct |
258 ms |
47956 KB |
Output is correct |
35 |
Correct |
211 ms |
39384 KB |
Output is correct |
36 |
Correct |
214 ms |
43068 KB |
Output is correct |
37 |
Correct |
257 ms |
44448 KB |
Output is correct |
38 |
Correct |
252 ms |
52540 KB |
Output is correct |
39 |
Correct |
87 ms |
27736 KB |
Output is correct |
40 |
Correct |
308 ms |
47956 KB |
Output is correct |
41 |
Correct |
303 ms |
48708 KB |
Output is correct |
42 |
Correct |
382 ms |
57588 KB |
Output is correct |
43 |
Correct |
118 ms |
35784 KB |
Output is correct |
44 |
Correct |
232 ms |
39216 KB |
Output is correct |
45 |
Correct |
211 ms |
44624 KB |
Output is correct |
46 |
Correct |
187 ms |
44740 KB |
Output is correct |
47 |
Correct |
258 ms |
44596 KB |
Output is correct |
48 |
Correct |
748 ms |
82748 KB |
Output is correct |