#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
const ll inf = 1e18;
vector<ll> weights(m+1);
vector<map<int,vector<tuple<int,int,int>>>> adj(n);
vector<map<int,pair<ll,int>>> dist_color(n); // min dist to node y
// while changing color c from node x:
// x -> y throught node c, I changed color
// to node c
for (int i=0,u,v,c;i<m;i++) {
cin >> u >> v >> c >> weights[i];
--u,--v,--c;
adj[u][c].emplace_back(v,weights[i],i);
adj[v][c].emplace_back(u,weights[i],i);
if (u) { dist_color[u][c]=make_pair(inf,m); }
if (v) { dist_color[v][c]=make_pair(inf,m); }
}
weights[m]=-inf;
vector<ll> dist(n,inf);
dist[0] = 0;
priority_queue<tuple<ll,int,int>> q;
q.emplace(0,-1,0);
// BRUH :(
while(!q.empty()) {
auto [d,last_changed,x] = q.top(); q.pop();
if (last_changed == -1) {
if (d > dist[x]) { continue; }
// run pseudo-normal dijkstra
for (auto &[color,_] : adj[x]) {
int sz = (int)_.size();
ll sum = 0;
for (auto &[y,w,idx]: _) {
sum += w;
}
ll option = min(dist[x],
dist_color[x][color].first-weights[dist_color[x][color].second]);
for (auto &[y,w,idx]: _) {
if (idx == dist_color[x][color].second) { continue; }
if (sz == 1) {
if (cmin(dist[y],dist[x])) {
q.emplace(dist[y],-1,y);
}
} else {
// first option: I change this
if (cmin(dist[y],dist[x]+w)) {
if (cmin(dist_color[y][color].first,dist[x]+w)) {
dist_color[y][color].second=idx;
}
q.emplace(dist[y],-1,y);
} else if (cmin(dist_color[y][color].first,dist[x]+w)) {
dist_color[y][color].second=idx;
q.emplace(dist[x]+w,color,y);
}
// second option: I change all others
ll now = sum-w+option;
if (cmin(dist[y],now)) {
q.emplace(now,-1,y);
}
}
}
}
} else {
if (d > dist_color[x][last_changed].first) { continue; }
int how_many = (int)adj[x][last_changed].size() - 1;
ll second_option = dist_color[x][last_changed].first;
for (auto &[y,w,idx]: adj[x][last_changed]) {
second_option+=w;
}
second_option -= weights[dist_color[x][last_changed].second];
for (auto &[y,w,idx]: adj[x][last_changed]) {
if (idx == dist_color[x][last_changed].second) { continue; }
if (how_many == 1) {
ll tot=d;
if (cmin(dist[y],tot)) {
q.emplace(tot,-1,y);
}
} else {
// first: change this one
ll tot=d+w;
if (cmin(dist[y],tot)) {
if (cmin(dist_color[y][last_changed].first,tot)) {
dist_color[y][last_changed].second=w;
}
q.emplace(tot,-1,y);
} else if (cmin(dist_color[y][last_changed].first,tot)) {
dist_color[y][last_changed].second=w;
q.emplace(tot,last_changed,y);
}
// second: change all the others
tot = second_option - w;
if (cmin(dist[y],tot)) {
q.emplace(tot,-1,y);
}
}
}
}
}
cout << (dist[n-1] == inf ? -1 : dist[n-1]) << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3024 ms |
18404 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
