Submission #1016379

#TimeUsernameProblemLanguageResultExecution timeMemory
1016379AiperiiiOlympic Bus (JOI20_ho_t4)C++14
100 / 100
765 ms3676 KiB
#include <bits/stdc++.h> //#define int long long #define all(x) x.begin(),x.end() #define ff first #define ss second #define pb push_back using namespace std; const int N=5e4+5; vector <pair <pair <int,int> ,int> > g[205]; int dist[205][205]; int a[N],b[N],c[N],d[N]; priority_queue <pair <int,int> > pq; signed main(){ ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); int n,m; cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ dist[i][j]=1e9; } dist[i][i]=0; } for(int i=1;i<=m;i++){ cin>>a[i]>>b[i]>>c[i]>>d[i]; dist[a[i]][b[i]]=min(dist[a[i]][b[i]],c[i]); g[a[i]].pb({{b[i],c[i]},i}); } for(int k=1;k<=n;k++){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]); } } } int mn=2e9; if(dist[1][n]<1e9 && dist[n][1]<1e9)mn=min(dist[1][n]+dist[n][1],mn); //cout<<mn<<"\n"; for(int i=1;i<=m;i++){ int new1n=min(dist[1][n],dist[1][b[i]]+dist[a[i]][n]+c[i]); int newn1=min(dist[n][1],dist[n][b[i]]+dist[a[i]][1]+c[i]); if(new1n==1e9 or newn1==1e9 or new1n+newn1+d[i]>=mn)continue; vector <int> dis(n+1,1e9); dis[1]=0; pq.push({0,1}); while(!pq.empty()){ int v=pq.top().ss; pq.pop(); if(v==b[i]){ if(dis[a[i]]>dis[b[i]]+c[i]){ dis[a[i]]=dis[b[i]]+c[i]; pq.push({dis[a[i]],a[i]}); } } for(auto to : g[v]){ if(to.ss==i)continue; if(dis[to.ff.ff]>dis[v]+to.ff.ss){ dis[to.ff.ff]=dis[v]+to.ff.ss; pq.push({dis[to.ff.ff],to.ff.ff}); } } } if(dis[n]!=1e9){ int ans=dis[n]; for(int j=1;j<=n;j++){ dis[j]=1e9; } dis[n]=0; pq.push({0,n}); while(!pq.empty()){ int v=pq.top().ss; pq.pop(); if(v==b[i]){ if(dis[a[i]]>dis[b[i]]+c[i]){ dis[a[i]]=dis[b[i]]+c[i]; pq.push({dis[a[i]],a[i]}); } } for(auto to : g[v]){ if(to.ss==i)continue; if(dis[to.ff.ff]>dis[v]+to.ff.ss){ dis[to.ff.ff]=dis[v]+to.ff.ss; pq.push({dis[to.ff.ff],to.ff.ff}); } } } if(dis[1]<1e9 && d[i]<1e9)mn=min(mn,ans+dis[1]+d[i]); } } if(mn==2e9)mn=-1; cout<<mn<<"\n"; } //g[1]-r //dis[0] 1 //dis[1] 1r //dis[2] n //dis[3] nr /* */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...