제출 #956537

#제출 시각아이디문제언어결과실행 시간메모리
956537pragmatistCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
218 ms26904 KiB
#include <bits/stdc++.h> using namespace std; const int N = (int)1e5+20; const int inf = (int)1e9+7; const long long INF = (long long)1e18+7; const int MOD = 42043; int sum(int x, int y) { x += y; if(x >= MOD) { x -= MOD; } return x; } int mult(int x, int y) { return 1ll*x*y%MOD; } struct Edge { int u, v, w; }; int n, m, s1, t1, s2, t2; vector<pair<int, int> > g[N]; vector<int> g2[N]; long long d[4][N]; void dijkstra(int tp, int s) { fill(d[tp], d[tp]+1+n, INF); d[tp][s] = 0; priority_queue<pair<long long, int> > q; q.push({0, s}); while(!q.empty()) { long long cur_d = -q.top().first; int v = q.top().second; q.pop(); if(cur_d>d[tp][v]) { continue; } for(auto [to, w] : g[v]) { if(d[tp][v]+w < d[tp][to]) { d[tp][to] = d[tp][v]+w; q.push({-d[tp][to], to}); } } } } bool used[N]; long long ans, mn1[N], mn2[N]; void dfs(int v) { used[v] = 1; mn1[v] = d[2][v]; mn2[v] = d[3][v]; for(auto to : g2[v]) { if(!used[to]) { dfs(to); } mn1[v] = min(mn1[v], mn1[to]); mn2[v] = min(mn2[v], mn2[to]); } ans = min(ans, d[2][v]+mn2[v]); ans = min(ans, d[3][v]+mn1[v]); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m >> s1 >> t1 >> s2 >> t2; vector<Edge> e; for(int i = 1; i <= m; ++i) { int u, v, w; cin >> u >> v >> w; e.push_back({u, v, w}); g[u].push_back({v, w}); g[v].push_back({u, w}); } dijkstra(0, s1); dijkstra(1, t1); dijkstra(2, s2); dijkstra(3, t2); ans = d[2][t2]; for(auto [u, v, w] : e) { if(d[0][u]+w+d[1][v]==d[0][t1]) { g2[u].push_back(v); } if(d[1][u]+w+d[0][v]==d[0][t1]) { g2[v].push_back(u); } } for(int i = 1; i <= n; ++i) { if(!used[i]) { dfs(i); } } cout << ans; 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...