Submission #874317

#TimeUsernameProblemLanguageResultExecution timeMemory
874317tsumondaiCommuter Pass (JOI18_commuter_pass)C++14
100 / 100
364 ms91568 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define fi first #define se second #define pb push_back #define mp make_pair #define foru(i, l, r) for(int i = l; i <= r; i++) #define ford(i, r, l) for(int i = r; i >= l; i--) #define __TIME (1.0 * clock() / CLOCKS_PER_SEC) typedef pair<int, int> ii; typedef pair<ii, int> iii; typedef pair<ii, ii> iiii; const int N = 1e6 + 5; const int oo = 1e18, mod = 1e9 + 7; int n, m, k, points[5], vis[N], dpU[N], dpV[N], ans; vector<ii> adj[N]; vector<int> dag[N]; int dist[N][5]; bool mini(int &a, const int b) { if (a > b) { a = b; return true; } else { return false; } } bool maxi(int &a, const int b) { if (a < b) { a = b; return true; } else { return false; } } void dfs(int x, int p) { if (vis[x]) return; vis[x] = 1; for (int y : dag[x]) { if (y != p) { dfs(y, x); dpU[x] = min({dpU[x], dpU[y], dist[y][3]}); dpV[x] = min({dpV[x], dpV[y], dist[y][4]}); } } ans = min(ans, dpU[x] + dist[x][4]); ans = min(ans, dpV[x] + dist[x][3]); } void dijkstra(int s) { foru(i, 1, n) dist[i][s] = oo; priority_queue <pair <long long, int>> pq; pq.push(make_pair(dist[points[s]][s] = 0, points[s])); while (!pq.empty()) { //auto [du, u] = pq.top(); pq.pop(); pair<long long, long long> tmp = pq.top(); pq.pop(); long long du = tmp.first, u = tmp.second; du = -du; if (du != dist[u][s]) continue; /* for (auto [w, v]: adj[u]) if (dist[v] > du + w) { dist[v] = du + w; pq.push(make_pair(-dist[v], v)); }*/ for (pair<long long, long long> nxt : adj[u]) if (dist[nxt.second][s] > du + nxt.first) { dist[nxt.second][s] = du + nxt.first; pq.push(make_pair(-dist[nxt.second][s], nxt.second)); } } } void process() { cin >> n >> m;// 1 2 3 4 foru(i, 1, 4) cin >> points[i]; foru(i, 1, m) { int u, v, c; cin >> u >> v >> c; adj[u].pb({c, v}); adj[v].pb({c, u}); } foru(i, 1, 4) dijkstra(i); foru(x, 1, n) { for (auto tmp : adj[x]) { int y = tmp.se, w = tmp.fi; if (dist[x][1] + w + dist[y][2] == dist[points[2]][1]) { dag[x].pb(y); } } } ans = dist[points[3]][4]; memset(dpU, 0x3f, sizeof(dpU)); memset(dpV, 0x3f, sizeof(dpV)); dfs(points[1], 0); cout << ans; return; } signed main() { cin.tie(0)->sync_with_stdio(false); //freopen(".inp", "r", stdin); //freopen(".out", "w", stdout); process(); cerr << "Time elapsed: " << __TIME << " s.\n"; 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...