#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];
}
int res = min((long long)1e17, (long long)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+von0_r[start]) + min(von0[v-1], von0[ende]+kosten+vonn_r[start]) + umdrehkosten);
}
}
if(res<1e17) cout << res;
else cout << -1;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
324 KB |
Output is correct |
3 |
Correct |
2 ms |
460 KB |
Output is correct |
4 |
Correct |
2 ms |
556 KB |
Output is correct |
5 |
Correct |
1 ms |
460 KB |
Output is correct |
6 |
Correct |
1 ms |
324 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
468 KB |
Output is correct |
10 |
Incorrect |
16 ms |
552 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
63 ms |
9152 KB |
Output is correct |
2 |
Correct |
66 ms |
9164 KB |
Output is correct |
3 |
Correct |
65 ms |
9292 KB |
Output is correct |
4 |
Correct |
3 ms |
624 KB |
Output is correct |
5 |
Correct |
2 ms |
460 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
328 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
34 ms |
9300 KB |
Output is correct |
10 |
Correct |
35 ms |
9344 KB |
Output is correct |
11 |
Correct |
67 ms |
9284 KB |
Output is correct |
12 |
Correct |
56 ms |
9260 KB |
Output is correct |
13 |
Correct |
56 ms |
9312 KB |
Output is correct |
14 |
Correct |
65 ms |
9580 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
460 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
312 ms |
7076 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
632 ms |
9096 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
289 ms |
9072 KB |
Output is correct |
9 |
Correct |
298 ms |
9260 KB |
Output is correct |
10 |
Correct |
438 ms |
9036 KB |
Output is correct |
11 |
Correct |
375 ms |
9164 KB |
Output is correct |
12 |
Correct |
474 ms |
8996 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
324 KB |
Output is correct |
17 |
Correct |
1 ms |
320 KB |
Output is correct |
18 |
Correct |
1 ms |
320 KB |
Output is correct |
19 |
Correct |
407 ms |
9060 KB |
Output is correct |
20 |
Correct |
386 ms |
9036 KB |
Output is correct |
21 |
Correct |
409 ms |
9036 KB |
Output is correct |
22 |
Correct |
411 ms |
9036 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
324 KB |
Output is correct |
3 |
Correct |
2 ms |
460 KB |
Output is correct |
4 |
Correct |
2 ms |
556 KB |
Output is correct |
5 |
Correct |
1 ms |
460 KB |
Output is correct |
6 |
Correct |
1 ms |
324 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
468 KB |
Output is correct |
10 |
Incorrect |
16 ms |
552 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |