Submission #1167628

#TimeUsernameProblemLanguageResultExecution timeMemory
1167628spycoderytOlympic Bus (JOI20_ho_t4)C++20
0 / 100
13 ms4676 KiB
#include <bits/stdc++.h> #define f first #define s second using namespace std; const int N = 205; #define int long long const int M = 50005; vector<pair<int,int> > A[N],B[N]; // actual and transpose pair<int,int> edges[M]; const int inf = 1e18; // int st[N],en[N],str[N],enr[N]; int weight[M],d[M]; int dis[4][N]; // st en str enr int tmp[N]; int opt[2][N]; void djik(int u,int k) { priority_queue<pair<int,int> > pq; // -w, i pq.push({0,u}); while(!pq.empty()) { auto [w,i] = pq.top();pq.pop(); w*=-1; if(w>dis[k][i])continue; for(auto [nxt,ei] : (k <= 1 ? A[i] : B[i])) { if(dis[k][nxt] > w + weight[ei]) { dis[k][nxt] = w + weight[ei]; if(k<=1){ opt[k][nxt] = ei; } pq.push({-dis[k][nxt], nxt}); } } } } void djik2(int st, int en,int exclude,map<int,int>&mp){ priority_queue<pair<int,int> > pq; // -w, i pq.push({0,st}); for(int i = 0;i<N;i++) tmp[i]=inf; tmp[st]=0; while(!pq.empty()) { auto [w,i] = pq.top();pq.pop(); w*=-1; if(w>tmp[i])continue; for(auto [nxt,ei] : A[i]) if(ei != exclude){ if(tmp[nxt] > w + weight[ei]) { tmp[nxt] = w + weight[ei]; pq.push({-tmp[nxt], nxt}); } } } mp[exclude]=tmp[en]; } int32_t main() { cin.tie(0)->sync_with_stdio(0); int n,m,a,b,ans=inf; cin >> n >> m; for(int i = 0;i<N;i++) for(int j = 0;j<4;j++)dis[j][i]=inf; dis[0][1] = dis[2][1] = 0; dis[1][n] = dis[3][n] = 0; for(int i = 1;i<=m;i++) { cin >> a >> b >> weight[i] >> d[i]; A[a].push_back({b,i}); B[b].push_back({a,i}); edges[i] = {a,b}; } djik(1,0); djik(n,1); djik(1,2); djik(n,3); // for(int j = 0;j<4;j++) { // for(int i = 1;i<=n;i++) cerr << dis[j][i] << " "; // cerr << "\n"; // } int x = n; set<int> frontpath,backpath; while(x!=1){ if(opt[0][x] == 0) break; else { int ei = opt[0][x]; x = edges[ei].f ^ edges[ei].s ^ x; frontpath.insert(ei); } } x = 1; while(x!=n) { if(opt[1][x] == 0) break; else { int ei = opt[1][x]; x = edges[ei].f ^ edges[ei].s ^ x; backpath.insert(ei); } } // for each edge in frontpath, find 1 -> n without using that edge map<int,int> frontlen,backlen; for(auto e : frontpath) { djik2(1,n,e,frontlen); } for(auto e : backpath) { djik2(n,1,e,backlen); } // for(auto e : frontpath) cerr << e << " "; // cerr<<"\n"; // for(auto [a,b] : frontlen) cerr << a << " " << b << "\n"; int front = dis[0][n], back = dis[1][1]; // cerr << front << " " << back << "\n"; ans = min(ans,front+back); for(int i = 1;i<=m;i++) { // st en str enr // invert first pass: st[a] + enr[b] + w + d, if m!+ then bck // if m in the thing then do it a = edges[i].f, b = edges[i].s; // if(dis[0][a] > dis[0][b])swap(a,b); int cur; cur = dis[0][a] + dis[3][b] + weight[i] + d[i]; if(backpath.find(i) != backpath.end()) { cur += backlen[i]; } else cur += back; ans = min(ans, cur); // inverst second pass cur = dis[1][b] + dis[2][a] + weight[i] + d[i]; if(frontpath.find(i) != frontpath.end()) { cur += frontlen[i]; }else cur += front; ans = min(ans,cur); swap(a,b); cur = dis[0][a] + dis[3][b] + weight[i] + d[i]; if(backpath.find(i) != backpath.end()) { cur += backlen[i]; } else cur += back; ans = min(ans, cur); // inverst second pass cur = dis[1][b] + dis[2][a] + weight[i] + d[i]; if(frontpath.find(i) != frontpath.end()) { cur += frontlen[i]; }else cur += front; ans = min(ans,cur); } cout << (ans >= inf ? -1 : ans); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...