| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 446442 | jamezzz | Olympic Bus (JOI20_ho_t4) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb emplace_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789123456789
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;
mt19937 rng(time(0));
#define maxn 205
#define maxm 50005
int n,m,u[maxm],v[maxm],c[maxm],d[maxm],dd[maxn];
int dist[maxn][maxn];
vi AL[maxn];
priority_queue<ii,vector<ii>,greater<ii>> pq;
int dij(int s,int t){
for(int i=0;i<n;++i)dd[i]=INF;
dd[s]=0;pq.push(ii(0,s));
while(!pq.empty()){
ii pr=pq.top();pq.pop();
if(dd[pr.se]<pr.fi)continue;
for(int i:AL[pr.se]){
if(dd[v[i]]>dd[u[i]]+c[i]){
dd[v[i]]=dd[u[i]]+c[i];
pq.push(ii(dd[v[i]],v[i]));
}
}
}
return dd[t];
}
int_32 main(){
sf("%lld%lld",&n,&m);
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
if(i!=j)dist[i][j]=INF;
}
}
for(int i=0;i<m;++i){
sf("%lld%lld%lld%lld",&u[i],&v[i],&c[i],&d[i]);
--u[i];--v[i];
mnto(dist[u[i]][v[i]],c[i]);
AL[u[i]].pb(i);
}
for(int k=0;k<n;++k){
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
mnto(dist[i][j],dist[i][k]+dist[k][j]);
}
}
}
int ans=min(INF,dist[0][n-1]+dist[n-1][0]);
for(int i=0;i<m;++i){
int d1=min(dist[0][n-1],dist[0][v[i]]+c[i]+dist[u[i]][n-1]);
int d2=min(dist[n-1][0],dist[n-1][v[i]]+c[i]+dist[u[i]][0]);
if(d1+d2+d[i]<ans){
AL[u[i]].erase(find(all(AL[u[i]]),i));
AL[v[i]].pb(i);
swap(u[i],v[i]);
mnto(ans,dij(0,n-1)+dij(n-1,0)+d[i]);
swap(u[i],v[i]);
AL[u[i]].pb(i);
AL[v[i]].pop_back();
}
}
if(ans==INF)ans=-1;
pf("%lld\n",ans);
}