#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];
map<int, long long> cost[MAXN][2];
void connect(int a, int b, int c, int h){
G[a].push_back({b, c, h});
G[b].push_back({a, c, h});
cost[a][0][c] = oo;
cost[a][1][c] = oo;
cost[b][0][c] = oo;
cost[b][1][c] = oo;
mapa[a][c];
mapa[b][c];
mapa[a][c] += h;
mapa[b][c] += h;
}
void dijkstra(){
priority_queue<tuple<long long, int, int, int, pair<int, int>>> Q;
Q.push({0, 1, 0, 0, {-1, 0}});
cost[1][0][0] = oo;
while(Q.size()){
auto [d, v, krawedz, plac, in] = Q.top();
Q.pop();
if(cost[v][plac][krawedz] <= -d) continue;
cost[v][plac][krawedz] = -d;
for(auto [u, c, h] : G[v]){
ll actcost;
//placimy za krawedz
actcost = h;
if(cost[u][1][c] > cost[v][plac][krawedz] + actcost)
Q.push({-(cost[v][plac][krawedz] + actcost), u, c, 1, {c, h}});
//nie placimy za nia
actcost = mapa[v][c] - h;
if(c == in.first)
actcost = max(actcost - (ll)in.second, (ll)0);
if(cost[u][0][c] > cost[v][plac][krawedz] + actcost)
Q.push({-(cost[v][plac][krawedz] + actcost), u, c, 0, {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);
}
dijkstra();
ll res = oo;
if(n == 1)
res = 0;
for(auto [u, c, h] : G[n])
res = min(res, min(cost[n][0][c], cost[n][1][c]));
if(res == oo)
res = -1;
cout << res << endl;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
16732 KB |
Output is correct |
2 |
Correct |
3 ms |
16732 KB |
Output is correct |
3 |
Correct |
4 ms |
16836 KB |
Output is correct |
4 |
Correct |
3 ms |
16732 KB |
Output is correct |
5 |
Correct |
4 ms |
16732 KB |
Output is correct |
6 |
Correct |
4 ms |
16728 KB |
Output is correct |
7 |
Correct |
11 ms |
18136 KB |
Output is correct |
8 |
Correct |
5 ms |
16988 KB |
Output is correct |
9 |
Correct |
553 ms |
85016 KB |
Output is correct |
10 |
Correct |
276 ms |
52132 KB |
Output is correct |
11 |
Correct |
6 ms |
17496 KB |
Output is correct |
12 |
Incorrect |
6 ms |
17500 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
444 ms |
67000 KB |
Output is correct |
2 |
Correct |
138 ms |
34500 KB |
Output is correct |
3 |
Correct |
522 ms |
62992 KB |
Output is correct |
4 |
Correct |
177 ms |
37320 KB |
Output is correct |
5 |
Execution timed out |
3020 ms |
334724 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
16732 KB |
Output is correct |
2 |
Correct |
3 ms |
16732 KB |
Output is correct |
3 |
Correct |
4 ms |
16836 KB |
Output is correct |
4 |
Correct |
3 ms |
16732 KB |
Output is correct |
5 |
Correct |
4 ms |
16732 KB |
Output is correct |
6 |
Correct |
4 ms |
16728 KB |
Output is correct |
7 |
Correct |
11 ms |
18136 KB |
Output is correct |
8 |
Correct |
5 ms |
16988 KB |
Output is correct |
9 |
Correct |
553 ms |
85016 KB |
Output is correct |
10 |
Correct |
276 ms |
52132 KB |
Output is correct |
11 |
Correct |
6 ms |
17496 KB |
Output is correct |
12 |
Incorrect |
6 ms |
17500 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |