제출 #959290

#제출 시각아이디문제언어결과실행 시간메모리
959290stefanneaguCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
492 ms25624 KiB
#include <bits/stdc++.h> #define int long long using namespace std; const int nmax = 1e5 + 1; vector<vector<pair<int, int>>> adj; int n; int pz[nmax], pt[nmax]; vector<int> calc(int a) { set<pair<int, int>> s; s.insert({0, a}); vector<int> v(n + 1, 1e18); v[a] = 0; while(!s.empty()) { auto curr = s.begin(); int sum = (*curr).first, i = (*curr).second; s.erase(*curr); if(v[i] < sum) { continue; } for(auto it : adj[i]) { if(v[it.first] > it.second + sum) { v[it.first] = it.second + sum; s.insert({it.second + sum, it.first}); } } } return v; } int32_t main() { int m; cin >> n >> m; int A, B, C, D; cin >> A >> B >> C >> D; adj.resize(n + 1); for(int i = 1; i <= m; i++) { int a, b, c; cin >> a >> b >> c; adj[a].push_back({b, c}); adj[b].push_back({a, c}); } vector<int> x = calc(A); vector<int> y = calc(B); vector<int> z = calc(C); vector<int> t = calc(D); vector<pair<int, int>> vp; for(int i = 1; i <= n; i++) { if(x[i] + y[i] == x[B]) { vp.push_back({x[i], i}); } } sort(vp.begin(), vp.end()); int ans = z[D]; for(auto i1 : vp) { int i = i1.second; pz[i] = z[i]; pt[i] = t[i]; for(auto it : adj[i]) { if(x[it.first] + it.second == x[i]) { pz[i] = min(pz[i], pz[it.first]); pt[i] = min(pt[i], pt[it.first]); } } ans = min(ans, pz[i] + t[i]); ans = min(ans, pt[i] + z[i]); } cout << 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...