제출 #1016226

#제출 시각아이디문제언어결과실행 시간메모리
1016226dwuyCommuter Pass (JOI18_commuter_pass)C++14
100 / 100
214 ms30608 KiB
#include <bits/stdc++.h> #define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL) #define fi first #define se second #define endl "\n" #define len(s) int32_t(s.length()) #define MASK(k)(1LL<<(k)) #define int long long using namespace std; typedef tuple<int, int, int> tpiii; typedef pair<double, double> pdd; typedef pair<int, int> pii; typedef long long ll; const long long OO = 1e18; const int MOD = 1e9 + 7; const int INF = 1e9; const int MX = 200005; int n, m; int S, T, U, V; vector<pii> G[MX]; void nhap(){ cin >> n >> m; cin >> S >> T >> U >> V; for(int i=1; i<=m; i++){ int u, v, c; cin >> u >> v >> c; G[u].push_back({v, c}); G[v].push_back({u, c}); } } void dijkstra(int u, int *d){ for(int i=1; i<=n; i++) d[i] = 1e18; priority_queue<pii> Q; Q.push({0, u}); d[u] = 0; while(Q.size()){ int du, u; tie(du, u) = Q.top(); du = -du; Q.pop(); if(du != d[u]) continue; for(pii &tmp: G[u]){ int v, c; tie(v, c) = tmp; c += du; if(c < d[v]){ d[v] = c; Q.push({-c, v}); } } } } int dS[MX], dT[MX], dU[MX], dV[MX]; int f1[MX], f2[MX]; void solve(){ dijkstra(S, dS); dijkstra(T, dT); dijkstra(U, dU); dijkstra(V, dV); int ans = dU[V]; vector<int> vt(n); for(int i=1; i<=n; i++) vt[i-1] = i; function<bool(const int &, const int &)> comp = [&](const int &a, const int &b){ return dS[a] < dS[b]; }; sort(vt.begin(), vt.end(), comp); for(int u: vt) if(dS[u] + dT[u] == dS[T]){ f1[u] = dU[u]; f2[u] = dV[u]; for(pii tmp: G[u]){ int v, c; tie(v, c) = tmp; if(dS[v] + c == dS[u]){ f1[u] = min(f1[u], f1[v]); f2[u] = min(f2[u], f2[v]); } } ans = min({ans, f1[u] + dV[u], f2[u] + dU[u]}); } cout << ans; } int32_t main(){ fastIO; //freopen("xebuyt.inp","r",stdin); //freopen("xebuyt.out","w",stdout); nhap(); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...