제출 #959878

#제출 시각아이디문제언어결과실행 시간메모리
959878happy_nodeOlympic Bus (JOI20_ho_t4)C++17
0 / 100
28 ms2900 KiB
#include <bits/stdc++.h> using namespace std; /* DIST(X,Y, [baru / ga baru]) N M log M buat dist x ke y tapi ga boleh langsung EDGE(X) -> edge terpendek dari Ux->Vx yang bukan dirinya sendiri Iterate semua edge, coba kalo dia yang diinvert Ada 3 kasus Let edge yg baru diinvert ke u->v 1. Pake edge yg diinvert buat pulang pergi dist(1, u) + dist(v, N) + dist(N, u) + dist(v, 1) 2. Pake edge yg diinvert buat pulang doang f(x) + dist(N,u) + dist(v, 1) f(x) = jarak terpendek dari 1 -> N tanpa menggunakan edge x f(x) 1. ga lewat u dan v 2. ga lewat u 3. ga lewat v 4. lewat u dan v kasus 1. dan 2. di handle sudah dengan ngeblock node v kasus 3. di handle dengan block node u kasus 4. artinya lewat u dan v namun ga lewat edge x 4.1 lewat u dulu baru v *) syarat ini -> dist(1,u) <= dist(1, v) 4.1.1 dari u -> v tapi ga pake edge (u,v) sama sekali f(x) = dist(1,u) + DIST(u,v,ga baru) + dist(v, N) 4.1.2 dari u -> v dan sempat pake edge (u,v) yang bukan edge x f(x) = dist(1,u) + EDGE(x) + dist(v, N) 4.2 lewat v dulu baru u *) syarat ini dist(1,v) <= dist(1, u) REV(x) = minimum dari semua edge v->u dist(1, v) + REV(x) + dist(u, N) 3. Pake edge yg diinvert buat pergi doang Subtask 2 itu bisa iterate semua edge terus langsung di minimum aja karena connectivity nya ngga berkurang, cuman bisa nambah.... */ const int MX=205; int N,M; int dist[MX][MX], U[MX], V[MX], C[MX], D[MX]; vector<array<int,2>> adj[MX]; void work(int src) { priority_queue<pair<int,int>> pq; pq.push({0,src}); dist[src][src]=0; while(!pq.empty()) { auto [d,v]=pq.top(); pq.pop(); d=-d; if(d>dist[src][v]) continue; for(auto [u,w]:adj[v]) { if(dist[src][u]>dist[src][v]+w) { dist[src][u]=dist[src][v]+w; pq.push({-dist[src][u],u}); } } } } int main() { cin.tie(0); ios_base::sync_with_stdio(0); for(int i=0;i<MX;i++) for(int j=0;j<MX;j++) dist[i][j]=2e9; cin>>N>>M; for(int i=0;i<M;i++) { int u,v,c,d; cin>>u>>v>>c>>d; U[i]=u; V[i]=v; C[i]=c; D[i]=d; adj[u].push_back({v,c}); } for(int i=1;i<=N;i++) work(i); int ans=2e9; if(dist[1][N]!=2e9 && dist[N][1]!=2e9) { ans=dist[1][N]+dist[N][1]; } for(int i=0;i<M;i++) { // 1 -> N : pake yg diflip ans=min(ans,D[i]+dist[1][V[i]]+dist[U[i]][N]+C[i]+dist[N][1]); // N -> 1 : pake yg diflip ans=min(ans,D[i]+dist[1][N]+dist[N][V[i]]+dist[U[i]][1]+C[i]); } cout<<ans<<'\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...