#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 7;
const ll oo = 1e18;
vector<tuple<int, int, int>> G[MAXN];
map<int, long long> mapa[MAXN];
ll cost[MAXN][3];
void connect(int a, int b, int c, int h){
G[a].push_back({b, c, h});
G[b].push_back({a, c, h});
mapa[a][c];
mapa[b][c];
mapa[a][c] += h;
mapa[b][c] += h;
}
void dijkstra(){
priority_queue<tuple<long long, int, int , pair<int, int>>> Q;
Q.push({0, 1, 0, {0, 0}});
// stan 0 przyszlismy taka gdzie zmieniamy wszystkie inne oprocz tej krawedzi
// stan 1 przyszlismy taka gdzie zmieniamy krawedz placac za nia
// stan 2 przyszlismy taka gdzie nie zmieniamy krawedzi przechodzimy za free
while(Q.size()){
auto [d, v, stan, in] = Q.top();
Q.pop();
if(cost[v][stan] <= -d) continue;
cost[v][stan] = -d;
for(auto [u, c, h] : G[v]){
ll costact;
if(stan == 0){
// chemy do 0
costact = mapa[v][c] - h;
if(cost[u][0] > cost[v][stan] + costact)
Q.push({-(cost[v][stan] + costact), u, 0, {0, 0}});
//chcemy do 1
costact = h;
if(cost[u][1] > cost[v][stan] + costact)
Q.push({-(cost[v][stan] + costact), u, 1, {c, h}});
// chemy do 2
costact = mapa[v][c] - h;
if(costact == 0)
if(cost[u][2] > cost[v][stan] + costact)
Q.push({-(cost[v][stan] + costact), u, 2, {0, 0}});
}
else if(stan == 1){
// chemy do 0
costact = mapa[v][c] - h;
if(c == in.first)
costact = max(costact - (ll)in.second, (ll)0);
if(cost[u][0] > cost[v][stan] + costact)
Q.push({-(cost[v][stan] + costact), u, 0, {0, 0}});
//chcemy do 1
costact = h;
if(cost[u][1] > cost[v][stan] + costact)
Q.push({-(cost[v][stan] + costact), u, 1, {c, h}});
// chemy do 2
costact = mapa[v][c] - h;
if(c == in.first)
costact = max(costact - (ll)in.second, (ll)0);
if(costact == 0)
if(cost[u][2] > cost[v][stan] + costact)
Q.push({-(cost[v][stan] + costact), u, 2, {0, 0}});
}
else{
// chemy do 0
costact = mapa[v][c] - h;
if(cost[u][0] > cost[v][stan] + costact)
Q.push({-(cost[v][stan] + costact), u, 0, {0, 0}});
//chcemy do 1
costact = h;
if(cost[u][1] > cost[v][stan] + costact)
Q.push({-(cost[v][stan] + costact), u, 1, {c, h}});
// chemy do 2
costact = mapa[v][c] - h;
if(costact == 0)
if(cost[u][2] > cost[v][stan] + costact)
Q.push({-(cost[v][stan] + costact), u, 2, {0, 0}});
}
}
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
for(int i = 1; i <= m; i++){
int a, b, c, h;
cin >> a >> b >> c >> h;
connect(a, b, c, h);
}
for(int i = 1; i <= n; i++)
cost[i][0] = cost[i][1] = cost[i][2] = oo;
dijkstra();
ll res;
res = min(cost[n][0], min(cost[n][1], cost[n][2]));
if(res == oo)
res = -1;
cout << res << endl;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
7516 KB |
Output is correct |
2 |
Correct |
2 ms |
7632 KB |
Output is correct |
3 |
Correct |
2 ms |
7516 KB |
Output is correct |
4 |
Correct |
2 ms |
7516 KB |
Output is correct |
5 |
Correct |
2 ms |
7516 KB |
Output is correct |
6 |
Correct |
2 ms |
7516 KB |
Output is correct |
7 |
Correct |
3 ms |
8028 KB |
Output is correct |
8 |
Correct |
2 ms |
7516 KB |
Output is correct |
9 |
Incorrect |
5 ms |
8152 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
171 ms |
30516 KB |
Output is correct |
2 |
Correct |
68 ms |
16984 KB |
Output is correct |
3 |
Correct |
186 ms |
31936 KB |
Output is correct |
4 |
Correct |
96 ms |
23628 KB |
Output is correct |
5 |
Incorrect |
763 ms |
58220 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
7516 KB |
Output is correct |
2 |
Correct |
2 ms |
7632 KB |
Output is correct |
3 |
Correct |
2 ms |
7516 KB |
Output is correct |
4 |
Correct |
2 ms |
7516 KB |
Output is correct |
5 |
Correct |
2 ms |
7516 KB |
Output is correct |
6 |
Correct |
2 ms |
7516 KB |
Output is correct |
7 |
Correct |
3 ms |
8028 KB |
Output is correct |
8 |
Correct |
2 ms |
7516 KB |
Output is correct |
9 |
Incorrect |
5 ms |
8152 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |