#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 200 + 6;
const ll inf = 1e13 + 7;
typedef pair<int,int> LL;
struct edge{
int v,c,id;
};
vector<edge> g[N],rg[N];
int n,m,u,v,c,inv,banned;
ll ans = inf,d[N],D[4][N];
bool dd[N],spec[100000];
void cond_to_all(ll scr,ll cond,ll Is_in){
memset(dd,0,sizeof(dd)); fill(d,d + n + 1,inf);
d[scr] = 0;
while(1){
ll x = inf,u = -1;
for (ll i = 1;i <= n;i++) if (d[i] < x && !dd[i]) x = d[i],u = i;
if (u == -1) break; dd[u] = 1;
for (auto i : g[u]){
ll v = i.v,L = i.c;
if (d[v] > d[u] + L && i.id != banned){
d[v] = d[u] + L;
if (Is_in) spec[i.id] = 1;
}
}
}
for (ll i = 1;i <= n;i++) D[cond][i] = d[i];
}
void all_to_cond(ll scr,ll cond,ll Is_in){
memset(dd,0,sizeof(dd)); fill(d,d + n + 1,inf);
d[scr] = 0;
while(1){
ll x = inf,u = -1;
for (ll i = 1;i <= n;i++) if (d[i] < x && !dd[i]) x = d[i],u = i;
if (u == -1) break; dd[u] = 1;
for (auto i : rg[u]){
ll v = i.v,L = i.c;
if (d[v] > d[u] + L && i.id != banned){
d[v] = d[u] + L;
if (Is_in) spec[i.id] = 1;
}
}
}
for (ll i = 1;i <= n;i++) D[cond][i] = d[i];
}
struct Road{
ll u,v,c,inv;
};
Road a[100000];
void Rev(ll id){
banned = id;
u = a[id].u; v = a[id].v; c = a[id].c;
g[v].push_back({u,c,m + 1}); rg[u].push_back({v,c,m + 1});
cond_to_all(1,0,0); cond_to_all(n,2,0); all_to_cond(1,1,0); all_to_cond(n,3,0);
ans = min(ans,D[0][n] + D[2][1] + a[id].inv);
g[v].pop_back(); rg[u].pop_back(); banned = 0;
cond_to_all(1,0,0); cond_to_all(n,2,0); all_to_cond(1,1,0); all_to_cond(n,3,0);
}
/// 0 : 1 to all 1 : all to 1 2 : n to all 3 : all to n
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#define task "tst"
if (fopen(task".INP","r")){
freopen(task".INP","r",stdin);
//freopen(task".OUT","w",stdout);
}
cin>>n>>m;
for (ll i = 1;i <= m;i++){
cin>>u>>v>>c>>inv; a[i] = {u,v,c,inv};
g[u].push_back({v,c,i}); rg[v].push_back({u,c,i});
}
cond_to_all(1,0,1); cond_to_all(n,2,1); all_to_cond(1,1,1); all_to_cond(n,3,1);
ans = D[0][n] + D[2][1];
ll cnt = 0;
for (ll i = 1;i <= m;i++) cnt += spec[i];
assert(cnt <= 4*n);
for (ll i = 1;i <= m;i++){
u = a[i].u; v = a[i].v; c = a[i].c;
if (!spec[i]){
//cout<<D[2][1]; return 0;
ll p = min(D[0][n],D[0][v] + c + D[3][u]),q = min(D[2][1],D[2][v] + c + D[1][u]);
ans = min(ans,p + q + a[i].inv); //cout<<p<<" x "<<D[2][v]; return 0;
}
else Rev(i);
}
cout<<(ans >= inf ? -1 : ans);
}
Compilation message
ho_t4.cpp: In function 'void cond_to_all(long long int, long long int, long long int)':
ho_t4.cpp:24:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
24 | if (u == -1) break; dd[u] = 1;
| ^~
ho_t4.cpp:24:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
24 | if (u == -1) break; dd[u] = 1;
| ^~
ho_t4.cpp: In function 'void all_to_cond(long long int, long long int, long long int)':
ho_t4.cpp:42:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
42 | if (u == -1) break; dd[u] = 1;
| ^~
ho_t4.cpp:42:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
42 | if (u == -1) break; dd[u] = 1;
| ^~
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:80:29: warning: narrowing conversion of 'i' from 'long long int' to 'int' [-Wnarrowing]
80 | g[u].push_back({v,c,i}); rg[v].push_back({u,c,i});
| ^
ho_t4.cpp:80:55: warning: narrowing conversion of 'i' from 'long long int' to 'int' [-Wnarrowing]
80 | g[u].push_back({v,c,i}); rg[v].push_back({u,c,i});
| ^
ho_t4.cpp:74:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
74 | freopen(task".INP","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
228 ms |
620 KB |
Output is correct |
| 2 |
Correct |
7 ms |
364 KB |
Output is correct |
| 3 |
Correct |
582 ms |
504 KB |
Output is correct |
| 4 |
Correct |
603 ms |
620 KB |
Output is correct |
| 5 |
Runtime error |
2 ms |
748 KB |
Execution killed with signal 6 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
27 ms |
7916 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
245 ms |
492 KB |
Output is correct |
| 2 |
Correct |
46 ms |
492 KB |
Output is correct |
| 3 |
Correct |
652 ms |
3180 KB |
Output is correct |
| 4 |
Correct |
27 ms |
492 KB |
Output is correct |
| 5 |
Correct |
700 ms |
4084 KB |
Output is correct |
| 6 |
Correct |
0 ms |
364 KB |
Output is correct |
| 7 |
Correct |
1 ms |
364 KB |
Output is correct |
| 8 |
Correct |
243 ms |
3948 KB |
Output is correct |
| 9 |
Correct |
228 ms |
3948 KB |
Output is correct |
| 10 |
Correct |
480 ms |
4204 KB |
Output is correct |
| 11 |
Correct |
473 ms |
3948 KB |
Output is correct |
| 12 |
Correct |
512 ms |
4076 KB |
Output is correct |
| 13 |
Correct |
1 ms |
364 KB |
Output is correct |
| 14 |
Correct |
0 ms |
364 KB |
Output is correct |
| 15 |
Correct |
1 ms |
364 KB |
Output is correct |
| 16 |
Correct |
1 ms |
364 KB |
Output is correct |
| 17 |
Correct |
1 ms |
364 KB |
Output is correct |
| 18 |
Correct |
0 ms |
364 KB |
Output is correct |
| 19 |
Correct |
472 ms |
4128 KB |
Output is correct |
| 20 |
Correct |
521 ms |
3948 KB |
Output is correct |
| 21 |
Correct |
491 ms |
4148 KB |
Output is correct |
| 22 |
Correct |
467 ms |
4076 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
228 ms |
620 KB |
Output is correct |
| 2 |
Correct |
7 ms |
364 KB |
Output is correct |
| 3 |
Correct |
582 ms |
504 KB |
Output is correct |
| 4 |
Correct |
603 ms |
620 KB |
Output is correct |
| 5 |
Runtime error |
2 ms |
748 KB |
Execution killed with signal 6 |
| 6 |
Halted |
0 ms |
0 KB |
- |
