#include<bits/stdc++.h>
#define int long long
using namespace std;
void dijkstra(vector<set<tuple<int,int,int>>>& adj, vector<long long>& dist, int start, vector<int>&parent){
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
dist[start] = 0;
pq.push({0,start});
while(!pq.empty()){
int wo = pq.top().second, preis = pq.top().first;
pq.pop();
if(dist[wo]== preis){
for(tuple<int,int,int> next: adj[wo]){
auto [ziel, kosten, umdrehkosten] = next;
if(dist[ziel] > preis+kosten){
dist[ziel] = preis+kosten;
parent[ziel] = wo;
pq.push({dist[ziel], ziel});
}
}
}
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int v, e; cin >> v >> e;
vector<set<tuple<int,int,int>>>adj(v), adj2(v);
vector<tuple<int,int,int,int>> edges(e);
for(int i=0; i<e; i++){
int a, b, c, d; cin >> a >> b >> c >> d;
a--; b--;
adj[a].insert(make_tuple(b,c,d));
adj2[b].insert(make_tuple(a,c,d));//umgedrehter Graph
edges[i] = make_tuple(a,b,c,d);
}
vector<long long> von0(v, 1e17), parent0(v, -1), vonn_r(v, 1e17), parent2(v, -1), vonn(v, 1e17), parentn(v, -1), von0_r(v, 1e17);
dijkstra(adj, von0, 0, parent0);
dijkstra(adj2, vonn_r, v-1, parent2);
dijkstra(adj2, von0_r, 0, parent2);
dijkstra(adj, vonn, v-1, parentn);
map<int,pair<int,int>> in_shortest_path;
int ort = v-1;
while(parent0[ort]!=-1){
in_shortest_path[parent0[ort]] = {ort, von0[ort]-von0[parent0[ort]]};
ort = parent0[ort];
}
ort = 0;
while(parentn[ort]!=-1){
in_shortest_path[parentn[ort]] = {ort, vonn[ort]-vonn[parentn[ort]]};
ort = parentn[ort];
}
if(von0[v-1]==1e17 && vonn[0]==1e17){
cout << -1;
exit(0);
}
int res = von0[v-1]+vonn[0];//keine Kante gedreht
for(int i=0; i<e; i++){
auto [start, ende, kosten, umdrehkosten] = edges[i];
pair<int,int> temp = {ende, kosten};
if(in_shortest_path[start] == temp){
adj[start].erase(make_tuple(ende, kosten, umdrehkosten));
adj[ende].insert(make_tuple(start, kosten, umdrehkosten));
vector<long long> dist(v, 1e17), p(v, -1), dist2(v, 1e17);
dijkstra(adj, dist, 0, p);
dijkstra(adj, dist2, v-1, p);
if(dist[v-1]<1e17 && dist2[0]<1e17) res = min(res, dist[v-1]+dist2[0]+umdrehkosten);
adj[start].insert(make_tuple(ende, kosten, umdrehkosten));
adj[ende].erase(make_tuple(start, kosten, umdrehkosten));
}else{
res = min(res, min(vonn[0], vonn[ende]+kosten+umdrehkosten+von0_r[start]) + min(von0[v-1], von0[ende]+kosten+umdrehkosten+vonn_r[start]));
}
}
if(res<1e17) cout << res;
else cout << -1;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
468 KB |
Output is correct |
4 |
Correct |
2 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
468 KB |
Output is correct |
10 |
Incorrect |
17 ms |
532 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
117 ms |
8200 KB |
Output is correct |
2 |
Correct |
172 ms |
8200 KB |
Output is correct |
3 |
Correct |
137 ms |
8116 KB |
Output is correct |
4 |
Correct |
4 ms |
596 KB |
Output is correct |
5 |
Correct |
2 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
408 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Incorrect |
38 ms |
8140 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
612 ms |
6460 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Execution timed out |
1088 ms |
8180 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
468 KB |
Output is correct |
4 |
Correct |
2 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
468 KB |
Output is correct |
10 |
Incorrect |
17 ms |
532 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |