제출 #1093456

#제출 시각아이디문제언어결과실행 시간메모리
1093456KindaGoodGamesCommuter Pass (JOI18_commuter_pass)C++14
31 / 100
1770 ms58044 KiB
/* Need to consider bidirectional path option. Idea was right, just implementation doesn't work :( */ #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> #define ll long long #define int ll #define pii pair<int,int> #define tiii tuple<int,int,int> #define tiiii tuple<int,int,int,int> using namespace std; ll INF = numeric_limits<ll>::max() / 2; int result(int n, int m, int s, int t, int ug, int vg, vector<vector<pii>>& adj, vector<int>&dist, vector<set<int>>& pre, vector<int>& dist2,vector<int>& distVG, vector<vector<int>>& adjSP) { // Shortest paths from s to t priority_queue<tiii, vector<tiii>, greater<tiii>> pq; // remove add help vertices queue<tiiii> q; map<pii, int> used; int mi = dist2[vg]; // cur | pre q.push({ t,t, INF, INF }); while (q.size()) { int v, u, d, ds; tie(v, u, d, ds) = q.front(); q.pop(); //adj[v].push_back({u,0}); // distance to go from any node in path to the goal int newd = min(d, distVG[v]); // distance to go to any node in path from start int newds = min(ds, dist2[v]); mi = min(mi, newds + newd); used[{v, u}]++; for (auto w : adjSP[v]) { if (used[{w, v}] < 1 && w != v)q.push({ w,v,newd,newds }); //if(!used.count({v,w}) && w != v)q.push({v,w,newd}); } } return min(mi, dist2[vg]); } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; int s, t; cin >> s >> t; s--; t--; int ug, vg; cin >> ug >> vg; ug--; vg--; vector<vector<pii>> adj(n); for (int i = 0; i < m; i++) { int a, b, c; cin >> a >> b >> c; a--; b--; adj[a].push_back({ b,c }); adj[b].push_back({ a,c }); } // Shortest paths from s to t vector<int> dists(n, INF); vector<set<int>> pres(n); priority_queue<tiii, vector<tiii>, greater<tiii>> pq; pq.push({ 0,s,s }); while (pq.size()) { int d, v, p; tie(d, v, p) = pq.top(); pq.pop(); if (dists[v] < d) continue; pres[v].insert(p); if (dists[v] == d) continue; dists[v] = d; for (auto pa : adj[v]) { pq.push({ pa.second + d, pa.first, v }); } } // Shortest paths from t to s vector<int> distt(n, INF); vector<set<int>> pret(n); pq.push({ 0,t,t }); while (pq.size()) { int d, v, p; tie(d, v, p) = pq.top(); pq.pop(); if (distt[v] < d) continue; pret[v].insert(p); if (distt[v] == d) continue; distt[v] = d; for (auto pa : adj[v]) { pq.push({ pa.second + d, pa.first, v }); } } // run Dijkstra again vector<int> dist2(n, INF); pq.push({ 0,ug,ug }); while (pq.size()) { int d, v, p; tie(d, v, p) = pq.top(); pq.pop(); if (dist2[v] <= d) continue; dist2[v] = d; for (auto pa : adj[v]) { pq.push({ pa.second + d, pa.first, v }); } } // run Dijkstra again vector<int> distVG(n, INF); pq.push({ 0,vg,vg }); while (pq.size()) { int d, v, p; tie(d, v, p) = pq.top(); pq.pop(); if (distVG[v] <= d) continue; distVG[v] = d; for (auto pa : adj[v]) { pq.push({ pa.second + d, pa.first, v }); } } // SP ADJ // SP Graph vector<vector<int>> adjSPS(n); vector<bool> vis(n); queue<int> qp; set<pii> us; qp.push(t); while (qp.size()) { int i = qp.front(); qp.pop(); if (vis[i]) continue; vis[i] = true; for (auto u : pres[i]) { if(!us.count({i,u})){ adjSPS[i].push_back(u); us.insert({i,u}); } //adjSP[u].push_back(i); if (!vis[u])qp.push(u); } } // SP Graph vector<vector<int>> adjSPT(n); qp = queue<int>(); us.clear(); vis = vector<bool>(n); qp.push(s); while (qp.size()) { int i = qp.front(); qp.pop(); if (vis[i]) continue; vis[i] = true; for (auto u : pret[i]) { if(!us.count({i,u})){ adjSPT[i].push_back(u); us.insert({i,u}); } //adjSP[u].push_back(i); if (!vis[u])qp.push(u); } } // Subcase 1 int a = result(n, m, s, t, ug, vg, adj, dists, pres, dist2, distVG, adjSPS); int b = result(n, m, t, s, vg, ug, adj, distt, pret, distVG,dist2, adjSPT); int c = result(n, m, t,s , ug, vg, adj, distt, pret, dist2, distVG, adjSPT); int d = result(n, m, s, t, vg ,ug, adj, dists, pres, distVG,dist2, adjSPS); cout << min({ a, b, c,d}) << "\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...