Submission #527639

#TimeUsernameProblemLanguageResultExecution timeMemory
527639LoboOlympic Bus (JOI20_ho_t4)C++17
100 / 100
313 ms6112 KiB
#include<bits/stdc++.h> using namespace std; const long long inf = (long long) 1e18 + 10; const int inf1 = (int) 1e9 + 10; #define int long long #define dbl long double #define endl '\n' #define sc second #define fr first #define mp make_pair #define pb push_back #define all(x) x.begin(), x.end() #define maxn 210 #define maxm 50010 int n, m, d[maxn][maxn], dx1[maxn][maxn], dxn[maxn][maxn], dxi1[maxn][maxn], dxin[maxn][maxn]; pair<int,int> mn1[maxn], mnn[maxn]; int u[maxm], v[maxm], c[maxm], up[maxm], mark[maxn]; vector<int> g[maxn],gi[maxn]; void shpx1(int x) { for(int i = 1; i <= n; i++) { dx1[x][i] = inf; mark[i] = 0; } dx1[x][1] = 0; if(x == 1) return; int cnt = n; while(cnt--) { int a; int dist = inf; for(int i = 1; i <= n; i++) { if(!mark[i] && dx1[x][i] < dist) { dist = dx1[x][i]; a = i; } } if(dist == inf) return; mark[a] = 1; for(auto i : g[a]) { int b = v[i]; int w = c[i]; if(b == x) continue; if(dx1[x][b] > dx1[x][a] + w) { dx1[x][b] = dx1[x][a] + w; } } } } void shpxi1(int x) { for(int i = 1; i <= n; i++) { dxi1[x][i] = inf; mark[i] = 0; } dxi1[x][1] = 0; if(x == 1) return; int cnt = n; while(cnt--) { int a; int dist = inf; for(int i = 1; i <= n; i++) { if(!mark[i] && dxi1[x][i] < dist) { dist = dxi1[x][i]; a = i; } } if(dist == inf) return; mark[a] = 1; for(auto i : gi[a]) { int b = u[i]; int w = c[i]; if(b == x) continue; if(dxi1[x][b] > dxi1[x][a] + w) { dxi1[x][b] = dxi1[x][a] + w; } } } } void shpxin(int x) { for(int i = 1; i <= n; i++) { dxin[x][i] = inf; mark[i] = 0; } dxin[x][n] = 0; if(x == n) return; int cnt = n; while(cnt--) { int a; int dist = inf; for(int i = 1; i <= n; i++) { if(!mark[i] && dxin[x][i] < dist) { dist = dxin[x][i]; a = i; } } if(dist == inf) return; mark[a] = 1; for(auto i : gi[a]) { int b = u[i]; int w = c[i]; if(b == x) continue; if(dxin[x][b] > dxin[x][a] + w) { dxin[x][b] = dxin[x][a] + w; } } } } void shpxn(int x) { for(int i = 1; i <= n; i++) { dxn[x][i] = inf; mark[i] = 0; } dxn[x][n] = 0; if(x == n) return; int cnt = n; while(cnt--) { int a; int dist = inf; for(int i = 1; i <= n; i++) { if(!mark[i] && dxn[x][i] < dist) { dist = dxn[x][i]; a = i; } } if(dist == inf) return; mark[a] = 1; for(auto i : g[a]) { int b = v[i]; int w = c[i]; if(b == x) continue; if(dxn[x][b] > dxn[x][a] + w) { dxn[x][b] = dxn[x][a] + w; } } } } void solve() { cin >> n >> m; for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { d[i][j] = inf; } } for(int i = 1; i <= n; i++) { d[i][i] = 0; } for(int i = 1; i <= m; i++) { cin >> u[i] >> v[i] >> c[i] >> up[i]; g[u[i]].pb(i); gi[v[i]].pb(i); d[u[i]][v[i]] = min(d[u[i]][v[i]],c[i]); } for(int k = 1; k <= n; k++) { for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { d[i][j] = min(d[i][j],d[i][k]+d[k][j]); } } } //tenho que pegar dx1 e dxn for(int i = 1; i <= n; i++) { shpx1(i); shpxn(i); shpxi1(i); shpxin(i); } //pegar o menor/segundo menor de cada cara for(int a = 1; a <= n; a++) { mn1[a] = mp(inf,inf); if(a == n) mn1[a] = mp(0,0); for(auto i : g[a]) { int b = v[i]; mn1[a].sc = min(mn1[a].sc, dx1[b][a] + c[i] + dxin[a][b]); if(mn1[a].sc < mn1[a].fr) swap(mn1[a].fr,mn1[a].sc); } } for(int a = 1; a <= n; a++) { mnn[a] = mp(inf,inf); if(a == 1) mnn[a] = mp(0,0); for(auto i : g[a]) { int b = v[i]; mnn[a].sc = min(mnn[a].sc, dxn[b][a] + c[i] + dxi1[a][b]); if(mnn[a].sc < mnn[a].fr) swap(mnn[a].fr,mnn[a].sc); } } int ans = inf; ans = min(ans, d[1][n]+d[n][1]); //usa no 1->n for(int i = 1; i <= m; i++) { int ans1 = 0; if(d[n][1] == d[n][u[i]] + c[i] + d[v[i]][1]) { ans1 = min(dxn[u[i]][1], mnn[u[i]].sc); } else { ans1 = d[n][1]; } ans1 = min(ans1,dxn[u[i]][v[i]]+c[i]+dxi1[v[i]][u[i]]); //d(n,v[i]) sem passar pro u[i] //d(u[i],1) sem passar por v[i] ans1+= dx1[u[i]][v[i]] + c[i] + up[i] + dxin[v[i]][u[i]]; ans = min(ans,ans1); } //usa no n->1 for(int i = 1; i <= m; i++) { int ans1 = 0; if(d[1][n] == d[1][u[i]] + c[i] + d[v[i]][n]) { ans1 = min(dx1[u[i]][n], mn1[u[i]].sc); } else { ans1 = d[1][n]; } ans1 = min(ans1,dx1[u[i]][v[i]]+c[i]+dxin[v[i]][u[i]]); ans1+= dxn[u[i]][v[i]] + c[i] + up[i] + dxi1[v[i]][u[i]]; ans = min(ans,ans1); } if(ans == inf) cout << -1 << endl; else cout << ans << endl; } int32_t main() { ios::sync_with_stdio(false); cin.tie(0); // freopen("in.in", "r", stdin); //freopen("out.out", "w", stdout); int tt = 1; // cin >> tt; while(tt--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...