제출 #285963

#제출 시각아이디문제언어결과실행 시간메모리
285963glikcakbnCommuter Pass (JOI18_commuter_pass)C++14
15 / 100
1875 ms262148 KiB
#include <iostream> #include <vector> #include <queue> #include <utility> #define pii pair<int, int> #define piii pair<int, pii> #define pll pair<long long, long long> #define plll pair<long long, pll> #define ff first #define ss second #define ee ss.ff #define rr ss.ss using namespace std; vector<pii> gph[101010]; vector<pii> agph[101010]; vector<pii> bgph[101010]; long long dist[101010]; vector<int> pr[101010]; void dfs(int x) { if(x == -1) return; for(auto y : pr[x]) { agph[x].push_back({y, 0}); bgph[y].push_back({x, 0}); dfs(y); } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; int s, t, u, v; cin >> s >> t >> u >> v; --s; --t; --u; --v; for(int i = 0; i < m; ++i) { int s, e, x; cin >> s >> e >> x; --s; --e; gph[s].push_back({e, x}); agph[s].push_back({e, x}); bgph[s].push_back({e, x}); gph[e].push_back({s, x}); agph[e].push_back({s, x}); bgph[e].push_back({s, x}); } { for(int i = 0; i < n; ++i) dist[i] = -1; priority_queue<plll, vector<plll>, greater<plll>> Q; Q.push({0, {s, -1}}); while(Q.size()) { auto x = Q.top(); Q.pop(); if(dist[x.ee] == -1 || dist[x.ee] == x.ff) pr[x.ee].push_back(x.rr); if(dist[x.ee] != -1) continue; dist[x.ee] = x.ff; for(auto y : gph[x.ee]) Q.push({x.ff + y.ss, {y.ff, x.ee}}); } // for(int i = 0; i < n; ++i) // { // for(auto x : pr[i]) cout << x << ' '; // cout << endl; // } dfs(t); } long long ans; { for(int i = 0; i < n; ++i) dist[i] = -1; priority_queue<pll, vector<pll>, greater<pll>> Q; Q.push({0, u}); while(Q.size()) { auto x = Q.top(); Q.pop(); if(dist[x.ss] != -1) continue; dist[x.ss] = x.ff; for(auto y : agph[x.ss]) Q.push({x.ff + y.ss, y.ff}); } ans = dist[v]; } { for(int i = 0; i < n; ++i) dist[i] = -1; priority_queue<pll, vector<pll>, greater<pll>> Q; Q.push({0, u}); while(Q.size()) { auto x = Q.top(); Q.pop(); if(dist[x.ss] != -1) continue; dist[x.ss] = x.ff; for(auto y : bgph[x.ss]) Q.push({x.ff + y.ss, y.ff}); } ans = min(ans, dist[v]); } 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...