#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Edge{
int to, c, p, id;
};
struct State{
int node, prevEdge, colorLater;
ll cost;
};
bool cmp(const State& a, const State& b){
return a.cost > b.cost;
}
const ll INF = 1e18;
const int MAXN = 1e5 + 5, MAXM = 2e5 + 5;
int n, m;
map<int, vector<Edge>> arr[MAXN];
map<int, ll> recolor[MAXN];
ll dp[MAXN];
int edge_color[MAXM], edge_cost[MAXM];
map<int, ll> dp2[MAXN];
int main(){
cin.tie(0)->sync_with_stdio(0);
// freopen("file.in", "r", stdin);
// freopen("file.out", "w", stdout);
cin >> n >> m;
for (int i=0; i<m; i++){
int s, e, c, p;
cin >> s >> e >> c >> p;
s--; e--;
recolor[s][c] += p;
recolor[e][c] += p;
arr[s][c].push_back({e, c, p, i});
arr[e][c].push_back({s, c, p, i});
edge_color[i] = c;
edge_cost[i] = p;
}
for (int i=0; i<n; i++){
dp[i] = INF;
}
priority_queue<State, vector<State>, decltype(&cmp)> pq(cmp);
pq.push({0, -1, 0, 0});
dp[0] = 0;
while (!pq.empty()){
State curr = pq.top();
pq.pop();
// cout << curr.cost << "\n";
if (curr.colorLater == 1){
if (dp2[curr.node][edge_color[curr.prevEdge]] != curr.cost){
continue;
}
for (Edge e : arr[curr.node][edge_color[curr.prevEdge]]){
if (e.id == curr.prevEdge){
continue;
}
ll nc = curr.cost + recolor[curr.node][e.c] - e.p;
if (nc < dp[e.to]){
pq.push({e.to, e.id, 0, nc});
dp[e.to] = nc;
}
}
}else{
if (dp[curr.node] != curr.cost){
continue;
}
for (auto& s : arr[curr.node]){
for (Edge e : s.second){
if (e.id == curr.prevEdge){
continue;
}
// Recolor edge e, but we don't plan to go through another edge of color e.c (explore all possibilities)
ll case1 = curr.cost + e.p;
if (case1 < dp[e.to]){
dp[e.to] = case1;
pq.push({e.to, e.id, 0, case1});
}
// Recolor all other edges
ll case2 = curr.cost + recolor[curr.node][e.c] - e.p;
if (case2 < dp[e.to]){
dp[e.to] = case2;
pq.push({e.to, e.id, 0, case2});
}
// Recolor edge e, and we will go through another edge of color e.c. We will recolor edge e when we get
// to e.to, by recoloring all other edges of color e.c (since we will go through another edge of e.c).
ll case3 = curr.cost;
if (!dp2[e.to].count(e.c) || case3 < dp2[e.to][e.c]){
dp2[e.to][e.c] = case3;
pq.push({e.to, e.id, 1, case3});
}
}
}
}
}
ll ans = dp[n-1];
if (ans == INF) ans = -1;
cout << ans << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
14412 KB |
Output is correct |
2 |
Correct |
10 ms |
14412 KB |
Output is correct |
3 |
Correct |
7 ms |
14412 KB |
Output is correct |
4 |
Correct |
7 ms |
14412 KB |
Output is correct |
5 |
Correct |
7 ms |
14412 KB |
Output is correct |
6 |
Correct |
7 ms |
14412 KB |
Output is correct |
7 |
Correct |
8 ms |
14596 KB |
Output is correct |
8 |
Correct |
8 ms |
14384 KB |
Output is correct |
9 |
Correct |
10 ms |
15052 KB |
Output is correct |
10 |
Correct |
9 ms |
14924 KB |
Output is correct |
11 |
Correct |
8 ms |
14796 KB |
Output is correct |
12 |
Correct |
8 ms |
14668 KB |
Output is correct |
13 |
Correct |
9 ms |
14796 KB |
Output is correct |
14 |
Correct |
12 ms |
14796 KB |
Output is correct |
15 |
Correct |
8 ms |
14668 KB |
Output is correct |
16 |
Correct |
9 ms |
14764 KB |
Output is correct |
17 |
Correct |
9 ms |
14772 KB |
Output is correct |
18 |
Correct |
8 ms |
14540 KB |
Output is correct |
19 |
Correct |
12 ms |
14676 KB |
Output is correct |
20 |
Correct |
10 ms |
14668 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
173 ms |
33388 KB |
Output is correct |
2 |
Correct |
65 ms |
23944 KB |
Output is correct |
3 |
Correct |
171 ms |
30304 KB |
Output is correct |
4 |
Correct |
99 ms |
27052 KB |
Output is correct |
5 |
Correct |
698 ms |
79144 KB |
Output is correct |
6 |
Correct |
550 ms |
68844 KB |
Output is correct |
7 |
Correct |
281 ms |
51212 KB |
Output is correct |
8 |
Correct |
349 ms |
48356 KB |
Output is correct |
9 |
Correct |
358 ms |
48280 KB |
Output is correct |
10 |
Correct |
267 ms |
45772 KB |
Output is correct |
11 |
Correct |
113 ms |
31684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
14412 KB |
Output is correct |
2 |
Correct |
10 ms |
14412 KB |
Output is correct |
3 |
Correct |
7 ms |
14412 KB |
Output is correct |
4 |
Correct |
7 ms |
14412 KB |
Output is correct |
5 |
Correct |
7 ms |
14412 KB |
Output is correct |
6 |
Correct |
7 ms |
14412 KB |
Output is correct |
7 |
Correct |
8 ms |
14596 KB |
Output is correct |
8 |
Correct |
8 ms |
14384 KB |
Output is correct |
9 |
Correct |
10 ms |
15052 KB |
Output is correct |
10 |
Correct |
9 ms |
14924 KB |
Output is correct |
11 |
Correct |
8 ms |
14796 KB |
Output is correct |
12 |
Correct |
8 ms |
14668 KB |
Output is correct |
13 |
Correct |
9 ms |
14796 KB |
Output is correct |
14 |
Correct |
12 ms |
14796 KB |
Output is correct |
15 |
Correct |
8 ms |
14668 KB |
Output is correct |
16 |
Correct |
9 ms |
14764 KB |
Output is correct |
17 |
Correct |
9 ms |
14772 KB |
Output is correct |
18 |
Correct |
8 ms |
14540 KB |
Output is correct |
19 |
Correct |
12 ms |
14676 KB |
Output is correct |
20 |
Correct |
10 ms |
14668 KB |
Output is correct |
21 |
Correct |
173 ms |
33388 KB |
Output is correct |
22 |
Correct |
65 ms |
23944 KB |
Output is correct |
23 |
Correct |
171 ms |
30304 KB |
Output is correct |
24 |
Correct |
99 ms |
27052 KB |
Output is correct |
25 |
Correct |
698 ms |
79144 KB |
Output is correct |
26 |
Correct |
550 ms |
68844 KB |
Output is correct |
27 |
Correct |
281 ms |
51212 KB |
Output is correct |
28 |
Correct |
349 ms |
48356 KB |
Output is correct |
29 |
Correct |
358 ms |
48280 KB |
Output is correct |
30 |
Correct |
267 ms |
45772 KB |
Output is correct |
31 |
Correct |
113 ms |
31684 KB |
Output is correct |
32 |
Correct |
111 ms |
26132 KB |
Output is correct |
33 |
Correct |
136 ms |
28216 KB |
Output is correct |
34 |
Correct |
351 ms |
47144 KB |
Output is correct |
35 |
Correct |
259 ms |
39216 KB |
Output is correct |
36 |
Correct |
253 ms |
45052 KB |
Output is correct |
37 |
Correct |
305 ms |
47632 KB |
Output is correct |
38 |
Correct |
294 ms |
57656 KB |
Output is correct |
39 |
Correct |
125 ms |
29084 KB |
Output is correct |
40 |
Correct |
368 ms |
48272 KB |
Output is correct |
41 |
Correct |
399 ms |
48460 KB |
Output is correct |
42 |
Correct |
435 ms |
57104 KB |
Output is correct |
43 |
Correct |
178 ms |
34996 KB |
Output is correct |
44 |
Correct |
368 ms |
39592 KB |
Output is correct |
45 |
Correct |
273 ms |
44740 KB |
Output is correct |
46 |
Correct |
238 ms |
45216 KB |
Output is correct |
47 |
Correct |
285 ms |
46872 KB |
Output is correct |
48 |
Correct |
684 ms |
76616 KB |
Output is correct |