#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;
int n, m;
map<int, vector<Edge>> arr[MAXN];
map<int, ll> recolor[MAXN];
ll dp[MAXN];
int edge_color[MAXN], edge_cost[MAXN];
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{
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";
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:28:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
28 | freopen("file.in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
14412 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
14412 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
14488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
14412 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
14412 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
