제출 #712245

#제출 시각아이디문제언어결과실행 시간메모리
712245dozerCommuter Pass (JOI18_commuter_pass)C++14
100 / 100
572 ms30688 KiB
#include <bits/stdc++.h> using namespace std; #define sp " " #define endl "\n"; #define fastio() cin.tie(0), ios_base::sync_with_stdio(0) #define pb push_back #define pii pair<int, int> #define st first #define nd second #define N 200005 #define int long long const int modulo = 1e9 + 7, INF = 2e18 + 7; int d[2][N]; pii dist[2][2][N]; vector<pii> adj[N]; pii neg(pii tmp) { return {-tmp.st, -tmp.nd}; } int32_t main() { fastio(); int n, m, s, t , u, v; cin>>n>>m; cin>>s>>t>>u>>v; for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) for (int k = 1; k <= n; k++) dist[i][j][k] = {INF, INF}, d[i][k] = INF; for (int i = 1; i <= m; i++) { int a, b, c; cin>>a>>b>>c; adj[a].pb({b, c}); adj[b].pb({a, c}); } auto dijkstra1 = [&](int root){ int curr = u; if (root) curr = v; priority_queue<pii> q; d[root][curr] = 0; q.push({0, curr}); while(!q.empty()) { int top = q.top().nd; q.pop(); for (auto i : adj[top]) { int to = i.st, w = i.nd; if (d[root][to] > d[root][top] + w) { d[root][to] = d[root][top] + w; q.push({-d[root][to], to}); } } } }; dijkstra1(0); dijkstra1(1); auto dijkstra2 = [&](int r1, int r2){ int curr = s; if (r1) curr = t; dist[r1][r2][curr] = {0, d[r2][curr]}; priority_queue<pair<pii ,int>> q; q.push({neg(dist[r1][r2][curr]), curr}); while(!q.empty()) { int top = q.top().nd; pii tmp = neg(q.top().st); q.pop(); for (auto i : adj[top]) { int to = i.st, w = i.nd; pii tmptmp = tmp; tmptmp.st += w; tmptmp.nd = min(tmptmp.nd, d[r2][to]); if (dist[r1][r2][to] > tmptmp) { dist[r1][r2][to] = tmptmp; q.push({neg(dist[r1][r2][to]), to}); } } } }; for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) dijkstra2(i, j); int ans = d[0][v]; for (int i = 1; i <= n; i++) { if (dist[0][0][i].st + dist[1][0][i].st == dist[0][0][t].st) { //cout<<i<<sp<<dist[0][0][i].nd<<sp<<dist[0][1][i].nd<<sp<<dist[1][0][i].nd<<sp<<dist[1][1][i].nd<<endl; ans = min(ans, dist[0][0][i].nd + dist[1][1][i].nd); ans = min(ans, dist[0][1][i].nd + dist[1][0][i].nd); } } cout<<ans<<endl; cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " seconds\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...