#include<bits/stdc++.h>
#include<iostream>
using namespace std;
const int MX = 2e5 + 5;
const long long INF = 1e18;
vector<int>g[MX/2];
int cost[MX], color[MX];
int edge[2][MX];
map<int,vector<int>>colored_edges[MX/2];
map<int, long long>ans[MX/2], sum[MX/2];
void PlayGround() {
int n, m;
cin>>n>>m;
for(int i=1, u,v,p,c; i<=m; ++i) {
cin>>u>>v>>c>>p;
g[u].push_back(i);
g[v].push_back(i);
color[i] = c, cost[i] = p;
edge[0][i] = u, edge[1][i] = v;
colored_edges[u][c].push_back(i);
colored_edges[v][c].push_back(i);
sum[v][c] += p;
sum[u][c] += p;
}
priority_queue<tuple<long long, int, int>>pq;
pq.emplace(0, 1, 0);
ans[1][0] = 0;
while(!pq.empty()) {
int v, nerfed;
long long c;
tie(c, v, nerfed) = pq.top();
pq.pop();
if(ans[v][nerfed]!=-c) continue;
if(nerfed) {
for(auto e : colored_edges[v][nerfed]) {
int to = edge[(edge[0][e]==v)][e];
long long cur = ans[v][nerfed] + sum[v][nerfed] - cost[e];
if(!ans[to].count(0) || ans[to][0]>cur) {
ans[to][0] = cur;
pq.emplace(-cur, to, 0);
}
}
} else {
for(auto e : g[v]) {
int to = edge[(edge[0][e]==v)][e];
long long cur = ans[v][nerfed] + sum[v][color[e]] - cost[e];
if(!ans[to].count(0) || ans[to][0]>cur) {
ans[to][0] = cur;
pq.emplace(-cur, to, 0);
}
cur = ans[v][nerfed];
if(!ans[to].count(color[e]) || ans[to][color[e]]>cur) {
ans[to][color[e]] = cur;
pq.emplace(-cur, to, color[e]);
}
cur = ans[v][nerfed] + cost[e];
if(!ans[to].count(0) || ans[to][0]>cur) {
ans[to][0] = cur;
pq.emplace(-cur, to, 0);
}
}
}
}
if(ans[n].count(0)==0) ans[n][0] = INF;
long long best = ans[n][0];
if(best==INF) best = -1;
cout<<best<<'\n';
}
int main() {
ios_base::sync_with_stdio();
cin.tie(nullptr);
PlayGround();
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
16724 KB |
Output is correct |
2 |
Correct |
10 ms |
16724 KB |
Output is correct |
3 |
Correct |
9 ms |
16644 KB |
Output is correct |
4 |
Correct |
8 ms |
16724 KB |
Output is correct |
5 |
Correct |
11 ms |
16724 KB |
Output is correct |
6 |
Correct |
9 ms |
16724 KB |
Output is correct |
7 |
Correct |
11 ms |
16852 KB |
Output is correct |
8 |
Correct |
13 ms |
16724 KB |
Output is correct |
9 |
Correct |
18 ms |
17496 KB |
Output is correct |
10 |
Correct |
12 ms |
17364 KB |
Output is correct |
11 |
Correct |
11 ms |
17188 KB |
Output is correct |
12 |
Correct |
11 ms |
17112 KB |
Output is correct |
13 |
Correct |
11 ms |
17180 KB |
Output is correct |
14 |
Correct |
11 ms |
17072 KB |
Output is correct |
15 |
Correct |
10 ms |
17064 KB |
Output is correct |
16 |
Correct |
13 ms |
17108 KB |
Output is correct |
17 |
Correct |
12 ms |
17092 KB |
Output is correct |
18 |
Correct |
9 ms |
16856 KB |
Output is correct |
19 |
Correct |
12 ms |
16980 KB |
Output is correct |
20 |
Correct |
11 ms |
17108 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
329 ms |
37252 KB |
Output is correct |
2 |
Correct |
121 ms |
27656 KB |
Output is correct |
3 |
Correct |
284 ms |
32096 KB |
Output is correct |
4 |
Correct |
164 ms |
30904 KB |
Output is correct |
5 |
Correct |
1210 ms |
90204 KB |
Output is correct |
6 |
Correct |
1029 ms |
79056 KB |
Output is correct |
7 |
Correct |
513 ms |
60956 KB |
Output is correct |
8 |
Correct |
584 ms |
54832 KB |
Output is correct |
9 |
Correct |
605 ms |
54924 KB |
Output is correct |
10 |
Correct |
480 ms |
51760 KB |
Output is correct |
11 |
Correct |
205 ms |
33948 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
16724 KB |
Output is correct |
2 |
Correct |
10 ms |
16724 KB |
Output is correct |
3 |
Correct |
9 ms |
16644 KB |
Output is correct |
4 |
Correct |
8 ms |
16724 KB |
Output is correct |
5 |
Correct |
11 ms |
16724 KB |
Output is correct |
6 |
Correct |
9 ms |
16724 KB |
Output is correct |
7 |
Correct |
11 ms |
16852 KB |
Output is correct |
8 |
Correct |
13 ms |
16724 KB |
Output is correct |
9 |
Correct |
18 ms |
17496 KB |
Output is correct |
10 |
Correct |
12 ms |
17364 KB |
Output is correct |
11 |
Correct |
11 ms |
17188 KB |
Output is correct |
12 |
Correct |
11 ms |
17112 KB |
Output is correct |
13 |
Correct |
11 ms |
17180 KB |
Output is correct |
14 |
Correct |
11 ms |
17072 KB |
Output is correct |
15 |
Correct |
10 ms |
17064 KB |
Output is correct |
16 |
Correct |
13 ms |
17108 KB |
Output is correct |
17 |
Correct |
12 ms |
17092 KB |
Output is correct |
18 |
Correct |
9 ms |
16856 KB |
Output is correct |
19 |
Correct |
12 ms |
16980 KB |
Output is correct |
20 |
Correct |
11 ms |
17108 KB |
Output is correct |
21 |
Correct |
329 ms |
37252 KB |
Output is correct |
22 |
Correct |
121 ms |
27656 KB |
Output is correct |
23 |
Correct |
284 ms |
32096 KB |
Output is correct |
24 |
Correct |
164 ms |
30904 KB |
Output is correct |
25 |
Correct |
1210 ms |
90204 KB |
Output is correct |
26 |
Correct |
1029 ms |
79056 KB |
Output is correct |
27 |
Correct |
513 ms |
60956 KB |
Output is correct |
28 |
Correct |
584 ms |
54832 KB |
Output is correct |
29 |
Correct |
605 ms |
54924 KB |
Output is correct |
30 |
Correct |
480 ms |
51760 KB |
Output is correct |
31 |
Correct |
205 ms |
33948 KB |
Output is correct |
32 |
Correct |
253 ms |
25288 KB |
Output is correct |
33 |
Correct |
280 ms |
29712 KB |
Output is correct |
34 |
Correct |
577 ms |
51860 KB |
Output is correct |
35 |
Correct |
450 ms |
43632 KB |
Output is correct |
36 |
Correct |
449 ms |
53448 KB |
Output is correct |
37 |
Correct |
545 ms |
55388 KB |
Output is correct |
38 |
Correct |
542 ms |
61284 KB |
Output is correct |
39 |
Correct |
313 ms |
27984 KB |
Output is correct |
40 |
Correct |
641 ms |
54920 KB |
Output is correct |
41 |
Correct |
655 ms |
55012 KB |
Output is correct |
42 |
Correct |
729 ms |
64232 KB |
Output is correct |
43 |
Correct |
314 ms |
37932 KB |
Output is correct |
44 |
Correct |
628 ms |
39908 KB |
Output is correct |
45 |
Correct |
496 ms |
52704 KB |
Output is correct |
46 |
Correct |
436 ms |
51672 KB |
Output is correct |
47 |
Correct |
473 ms |
55004 KB |
Output is correct |
48 |
Correct |
1259 ms |
90644 KB |
Output is correct |