#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
typedef long long ll;
const ll inf = 1e18;
const int MX = 5e4 + 5;
ll n, m, a[MX], b[MX], c[MX], d[MX], ans, chk[2][MX], mnd[2], d1, d2, D[4][205];
vector<pair<ll, ll>> adj[205], rev[205];
ll dijk(int s, int e, int f){
int t = n + 1 - s;
vector<ll> dist(n + 1, inf);
vector<int> E(n + 1, 0), vis(n + 1, 0);
dist[s] = 0;
while(1){
ll mn = inf, x;
for(int i = 1; i <= n; i++)
if(!vis[i] && dist[i] < mn) mn = dist[i], x = i;
if(mn == inf) break;
vis[x] = 1;
if(f == 1 || f == 3){
for(auto&[nx, ix] : rev[x])
if(ix != e && dist[x] + c[ix] < dist[nx]) dist[nx] = dist[x] + c[ix], E[nx] = ix;
}
else{
for(auto&[nx, ix] : adj[x])
if(ix != e && dist[x] + c[ix] < dist[nx]) dist[nx] = dist[x] + c[ix], E[nx] = ix;
}
}
if(f >= 4){
f -= 4;
if(dist[t] == inf) return inf;
for(int x = t; x != s; x = a[E[x]]) chk[f][E[x]] = 1;
}
else if(f >= 0) {
for(int i = 1; i <= n; i++) D[f][i] = dist[i];
}
return dist[t];
}
int main(void){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
for(int i = 0; i < m; i++){
cin >> a[i] >> b[i] >> c[i] >> d[i];
adj[a[i]].emplace_back(b[i], i);
rev[b[i]].emplace_back(a[i], i);
}
dijk(1, -1, 0);
dijk(n, -1, 1);
dijk(n, -1, 2);
dijk(1, -1, 3);
mnd[0] = dijk(1, -1, 4);
mnd[1] = dijk(n, -1, 5);
ans = mnd[0] + mnd[1];
for(int i = 0; i < m; i++){
adj[b[i]].emplace_back(a[i], m);
c[m] = c[i] + d[i];
if(!chk[0][i]) d1 = min(mnd[0], D[0][b[i]] + c[i] + d[i] + D[1][a[i]]);
else d1 = dijk(1, i, -1);
if(!chk[1][i]) d2 = min(mnd[1], D[2][b[i]] + c[i] + d[i] + D[3][a[i]]);
else d2 = dijk(n, i, -1);
//cout << d1 << ' ' << d2 << '\n';
ans = min(ans, d1 + d2);
adj[b[i]].pop_back();
}
cout << (ans >= inf ? -1 : ans);
return 0;
}
Compilation message
ho_t4.cpp: In function 'll dijk(int, int, int)':
ho_t4.cpp:24:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
24 | for(auto&[nx, ix] : rev[x])
| ^
ho_t4.cpp:28:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
28 | for(auto&[nx, ix] : adj[x])
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
472 KB |
Output is correct |
2 |
Correct |
0 ms |
344 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 |
480 KB |
Output is correct |
6 |
Correct |
1 ms |
344 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
416 KB |
Output is correct |
10 |
Correct |
33 ms |
468 KB |
Output is correct |
11 |
Correct |
32 ms |
468 KB |
Output is correct |
12 |
Correct |
32 ms |
468 KB |
Output is correct |
13 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
5632 KB |
Output is correct |
2 |
Correct |
17 ms |
5588 KB |
Output is correct |
3 |
Correct |
18 ms |
5672 KB |
Output is correct |
4 |
Correct |
2 ms |
468 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 |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Incorrect |
16 ms |
5520 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
408 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
12 ms |
4156 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
20 ms |
5380 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Incorrect |
14 ms |
5340 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
472 KB |
Output is correct |
2 |
Correct |
0 ms |
344 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 |
480 KB |
Output is correct |
6 |
Correct |
1 ms |
344 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
416 KB |
Output is correct |
10 |
Correct |
33 ms |
468 KB |
Output is correct |
11 |
Correct |
32 ms |
468 KB |
Output is correct |
12 |
Correct |
32 ms |
468 KB |
Output is correct |
13 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |