#pragma GCC optimize("O2")
#include <fstream>
#include <string>
#include <iostream>
#include <bitset>
#include <math.h>
#include <string>
#include <algorithm>
#include <assert.h>
#include <bits/stdc++.h>
#include <vector>
#include <queue>
#include<stdio.h>
#include<ctype.h>
#define ll long long
using namespace std;
int n, m;
struct con{
int d;
int color;
ll cost;
};
vector<con> cons[100001];
map<int, ll> cost[100001];
// how much to convert all nodes of a color to some other color
map<int, ll> dist[100001];
ll dist2[100001];
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
int one, two, three;
ll four;
for (int x = 0; x < m; x++){
cin >> one >> two >> three >> four;
cons[one - 1].push_back({two - 1, three, four});
cons[two - 1].push_back({one - 1, three, four});
}
for (int x = 0; x < n; x++){
for (int y = 0; y < cons[x].size(); y++){
int col = cons[x][y].color;
ll cst = cons[x][y].cost;
if (cost[x].find(col) == cost[x].end()){
cost[x][col] = cst;
} else {
cost[x][col] += cst;
}
}
dist2[x] = 1e18;
}
priority_queue<tuple<ll, int, int>> q;
//cost, node, color
q.push(make_tuple(0, 0, 0));
dist2[0] = 0;
while(q.size() > 0){
int node;
ll cst;
int color;
tie(cst, node, color) = q.top();
cst *= -1;
q.pop();
if (node == n - 1 && color == 0){
break;
}
if (color != 0){
if (cost != dist[node][color]){
continue;
}
//we need to go to a node with the same color
for (auto con: cons[node]){
if (con.color == color){
if (used[con.d].find(0) == used[con.d].end()){
ll ncost = cst + cost[node][color] - con.cost;
if (dist2[con.d] > ncost){
dist2[con.d] = ncost;
q.push(make_tuple(-1 * ncost, con.d, 0));
}
}
}
}
}
else{
if (cost != dist2[node]){
continue;
}
//there are 3 things which we can do
for (auto con: cons[node]){
//switch everything but the connection
ll ncost = cst + cost[node][con.color] - con.cost;
if (dist2[con.d] > ncost){
dist2[con.d] = ncost;
q.push(make_tuple(-1 * ncost, con.d, 0));
}
//switch our node only
ncost = cst + con.cost;
if (dist2[con.d] > ncost){
dist2[con.d] = ncost;
q.push(make_tuple(-1 * ncost, con.d, 0));
}
//dont switch anything and make the next node switch
ncost = cst;
if (dist[con.d].find(con.color) == dist[con.d].end() || (dist[con.d][con.color] > ncost && ncost < dist2[con.d] && cost[con.d][con.color] > con.cost)){
dist[con.d][con.color] = ncost;
q.push(make_tuple(-1 * ncost, con.d, con.color));
}
}
}
}
if (dist2[n - 1] == 1e18){
cout << -1 << "\n";
}
else{
cout << dist2[n - 1] << "\n";
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:46:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<con>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for (int y = 0; y < cons[x].size(); y++){
| ~~^~~~~~~~~~~~~~~~
Main.cpp:72:41: error: ISO C++ forbids comparison between pointer and integer [-fpermissive]
72 | if (cost != dist[node][color]){
| ^
Main.cpp:78:25: error: 'used' was not declared in this scope
78 | if (used[con.d].find(0) == used[con.d].end()){
| ^~~~
Main.cpp:89:35: error: ISO C++ forbids comparison between pointer and integer [-fpermissive]
89 | if (cost != dist2[node]){
| ^
