#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;
ll n, m;
struct con{
ll d;
ll color;
ll cost;
};
vector<con> cons[200001];
unordered_map<ll, ll> cost[200001];
// how much to convert all nodes of a color to some other color
unordered_map<ll, ll> dist[200001];
unordered_map<ll, ll> used[200001];
//if node with color x was used
int main(){
cin >> n >> m;
ll one, two, three, 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++){
ll 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;
}
}
}
priority_queue<tuple<ll, ll, ll>> q;
//cost, node, color
q.push(make_tuple(0, 0, 0));
while(q.size() > 0){
ll node;
ll cst;
ll color;
tie(cst, node, color) = q.top();
q.pop();
if (used[node].find(color) == used[node].end()){
used[node][color] = 1;
cst *= -1;
if (color != 0){
//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 (dist[con.d].find(0) == dist[con.d].end() || dist[con.d][0] > ncost){
dist[con.d][0] = ncost;
q.push(make_tuple(-1 * ncost, con.d, 0));
}
}
}
}
}
else{
//there are 3 things which we can do
for (auto con: cons[node]){
if (used[con.d].find(con.color) == used[con.d].end()){
//dont switch anything and make the next node switch
ll ncost = cst;
if (dist[con.d].find(con.color) == dist[con.d].end() || dist[con.d][con.color] > ncost && cost[con.d][con.color] > con.cost){
dist[con.d][con.color] = ncost;
q.push(make_tuple(-1 * ncost, con.d, con.color));
}
}
if (used[con.d].find(0) == used[con.d].end()){
//switch everything but the connection
ll ncost = cst + cost[node][con.color] - con.cost;
if (dist[con.d].find(0) == dist[con.d].end() || dist[con.d][0] > ncost){
dist[con.d][0] = ncost;
q.push(make_tuple(-1 * ncost, con.d, 0));
}
//switch our node only
ncost = cst + con.cost;
if (dist[con.d].find(0) == dist[con.d].end() || dist[con.d][0] > ncost){
dist[con.d][0] = ncost;
q.push(make_tuple(-1 * ncost, con.d, 0));
}
}
}
}
}
}
if (dist[n - 1].find(0) == dist[n - 1].end()){
cout << -1 << "\n";
}
else{
cout << dist[n - 1][0] << "\n";
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:44:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<con>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for (int y = 0; y < cons[x].size(); y++){
| ~~^~~~~~~~~~~~~~~~
Main.cpp:86:112: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
86 | if (dist[con.d].find(con.color) == dist[con.d].end() || dist[con.d][con.color] > ncost && cost[con.d][con.color] > con.cost){
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
26 ms |
37792 KB |
Output is correct |
2 |
Correct |
26 ms |
37872 KB |
Output is correct |
3 |
Correct |
26 ms |
37760 KB |
Output is correct |
4 |
Correct |
26 ms |
37872 KB |
Output is correct |
5 |
Correct |
27 ms |
37912 KB |
Output is correct |
6 |
Correct |
27 ms |
37836 KB |
Output is correct |
7 |
Correct |
28 ms |
37964 KB |
Output is correct |
8 |
Correct |
28 ms |
37932 KB |
Output is correct |
9 |
Correct |
36 ms |
38416 KB |
Output is correct |
10 |
Correct |
36 ms |
38276 KB |
Output is correct |
11 |
Correct |
30 ms |
38188 KB |
Output is correct |
12 |
Correct |
29 ms |
38204 KB |
Output is correct |
13 |
Correct |
30 ms |
38316 KB |
Output is correct |
14 |
Correct |
30 ms |
38220 KB |
Output is correct |
15 |
Correct |
29 ms |
38092 KB |
Output is correct |
16 |
Correct |
30 ms |
38152 KB |
Output is correct |
17 |
Correct |
31 ms |
38280 KB |
Output is correct |
18 |
Correct |
27 ms |
37848 KB |
Output is correct |
19 |
Correct |
30 ms |
38132 KB |
Output is correct |
20 |
Correct |
34 ms |
38144 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
310 ms |
55444 KB |
Output is correct |
2 |
Correct |
142 ms |
46972 KB |
Output is correct |
3 |
Correct |
318 ms |
54484 KB |
Output is correct |
4 |
Correct |
211 ms |
50616 KB |
Output is correct |
5 |
Execution timed out |
3060 ms |
78128 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
26 ms |
37792 KB |
Output is correct |
2 |
Correct |
26 ms |
37872 KB |
Output is correct |
3 |
Correct |
26 ms |
37760 KB |
Output is correct |
4 |
Correct |
26 ms |
37872 KB |
Output is correct |
5 |
Correct |
27 ms |
37912 KB |
Output is correct |
6 |
Correct |
27 ms |
37836 KB |
Output is correct |
7 |
Correct |
28 ms |
37964 KB |
Output is correct |
8 |
Correct |
28 ms |
37932 KB |
Output is correct |
9 |
Correct |
36 ms |
38416 KB |
Output is correct |
10 |
Correct |
36 ms |
38276 KB |
Output is correct |
11 |
Correct |
30 ms |
38188 KB |
Output is correct |
12 |
Correct |
29 ms |
38204 KB |
Output is correct |
13 |
Correct |
30 ms |
38316 KB |
Output is correct |
14 |
Correct |
30 ms |
38220 KB |
Output is correct |
15 |
Correct |
29 ms |
38092 KB |
Output is correct |
16 |
Correct |
30 ms |
38152 KB |
Output is correct |
17 |
Correct |
31 ms |
38280 KB |
Output is correct |
18 |
Correct |
27 ms |
37848 KB |
Output is correct |
19 |
Correct |
30 ms |
38132 KB |
Output is correct |
20 |
Correct |
34 ms |
38144 KB |
Output is correct |
21 |
Correct |
310 ms |
55444 KB |
Output is correct |
22 |
Correct |
142 ms |
46972 KB |
Output is correct |
23 |
Correct |
318 ms |
54484 KB |
Output is correct |
24 |
Correct |
211 ms |
50616 KB |
Output is correct |
25 |
Execution timed out |
3060 ms |
78128 KB |
Time limit exceeded |
26 |
Halted |
0 ms |
0 KB |
- |