| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 757148 | groshi | 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<iostream>#include<vector>#include<queue>#include<map>#define int long longusing namespace std;struct wi{ vector<int> Q; int odw=0; int kiedy_odw=1e18; int od_kogo=0;}*w;int wynik=1e18;int kiedy=1;int n;int t[60000][4];int odl[210][210];map<int,int> nalezy;void dijkstra(int kto){ priority_queue<pair<int,pair<int,int> > > kolejka; kolejka.push({0,{1,0}}); while(!kolejka.empty()) { pair<int,pair<int,int> > para=kolejka.top(); int x=para.second.first; kolejka.pop(); if(w[x].odw==kiedy) continue; w[x].od_kogo=para.second.second; w[x].odw=kiedy; w[x].kiedy_odw=-para.first; for(int i=0;i<w[x].Q.size();i++) { int ile=w[x].Q[i]; if(ile==kto) continue; int y; if(ile<0) y=t[-ile][3]; else y=t[ile][0]; int koszt=t[abs(ile)][1]; if(w[y].odw==kiedy) continue; kolejka.push({para.first-koszt,{y,ile}}); } } int d1=w[n].kiedy_odw; bool git1=0,git2=0; if(w[n].odw==kiedy) git1=1; if(kto==0 && w[n].odw==kiedy) { int jestem=n; while(jestem!=1) { nalezy[w[jestem].od_kogo]=1; int x,y; x=t[w[jestem].od_kogo][0]; y=t[w[jestem].od_kogo][3]; if(x==jestem) jestem=y; else jestem=x; } } kiedy++; kolejka.push({0,{n,0}}); while(!kolejka.empty()) { pair<int,pair<int,int> > para=kolejka.top(); int x=para.second.first; kolejka.pop(); if(w[x].odw==kiedy) continue; w[x].od_kogo=para.second.second; w[x].odw=kiedy; w[x].kiedy_odw=-para.first; for(int i=0;i<w[x].Q.size();i++) { int ile=w[x].Q[i]; if(ile==kto) continue; int y; if(ile<0) y=t[-ile][3]; else y=t[ile][0]; int koszt=t[abs(ile)][1]; if(w[y].odw==kiedy) continue; kolejka.push({para.first-koszt,{y,ile}}); } } if(w[1].odw==kiedy) git2=1; if(kto==0 && w[1].odw==kiedy) { int jestem=1; while(jestem!=n) { nalezy[w[jestem].od_kogo]=1; int x,y; x=t[w[jestem].od_kogo][0]; y=t[w[jestem].od_kogo][3]; if(x==jestem) jestem=y; else jestem=x; } } int d2=w[1].kiedy_odw; if(git1==1 && git2==1) wynik=min(wynik,d1+d2+t[kto][2]);}int32_t main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int m,x,y,a,b; cin>>n>>m; w=new wi[n+3]; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) odl[i][j]=1e18; for(int i=1;i<=m;i++) { cin>>x>>y>>a>>b; w[x].Q.push_back(i); t[i][0]=y; t[i][1]=a; t[i][2]=b; t[i][3]=x; odl[x][y]=min(odl[x][y],a); } for(int i=1;i<=n;i++) odl[i][i]=0; for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) odl[i][j]=min(odl[i][j],odl[i][k]+odl[k][j]); dijkstra(0); kiedy++; for(auto it=nalezy.begin();it!=nalezy.end();it++) { int i=it->first; int odwr=t[i][0]; int pocz=t[i][3]; w[odwr].Q.push_back(-i); dijkstra(i); kiedy++; w[odwr].Q.pop_back(); } for(int i=1;i<=m;i++) { if(nalezy.find(i)!=nalezy.end()) continue; int x=t[i][3]; int y=t[i][0]; int odwr=t[i][2]; int koszt=t[i][1]; wynik=min(wynik,odl[1][n]+odl[n][y]+odl[x][1]+odwr+koszt); wynik=min(wynik,odl[n][1]+odl[x][n]+odl[1][y]+odwr+koszt); wynik=min(wynik,odl[1][y]+odl[x][n]+odl[n][y]+odl[x][1]+odwr+2*koszt); } if(wynik>=1e18) cout<<"-1"; else cout<<wynik; return 0;}