제출 #1065671

#제출 시각아이디문제언어결과실행 시간메모리
1065671windowwifeCommuter Pass (JOI18_commuter_pass)C++14
100 / 100
234 ms70636 KiB
#include<bits/stdc++.h> #define ll long long #define task "" using namespace std; const int maxn = 1e6 + 2; ll n, m, a, b, c, d, dist[4][maxn], dp[4][maxn], u, v, w, res; bool visited[maxn], avail[maxn]; struct Edge { ll u, v, w; }edge[maxn]; vector<int> adj[maxn], dag[maxn], lst; struct Item { ll u, dist; bool operator < (const Item& other) const { return dist > other.dist; } }; priority_queue<Item> pq; bool minimize (ll &a, ll b) { if (a == -1 || a > b) { a = b; return true; } return false; } void topo (int u) { avail[u] = true; for (int v : dag[u]) if (!avail[v]) topo(v); lst.push_back(u); } void dijkstra (int x, int u) { memset(visited, 0, sizeof(visited)); for (int i = 1; i <= n; i++) dist[x][i] = -1; dist[x][u] = 0; pq.push({u, 0}); while (!pq.empty()) { int u = pq.top().u; pq.pop(); if (visited[u]) continue; visited[u] = true; for (int i : adj[u]) { int v = edge[i].u ^ edge[i].v ^ u; if (minimize(dist[x][v], dist[x][u] + edge[i].w)) pq.push({v, dist[x][v]}); } } } int main () { //freopen(task".INP", "r", stdin); //freopen(task".OUT", "w", stdout); ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m >> a >> b >> c >> d; for (int i = 1; i <= m; i++) { cin >> u >> v >> w; edge[i] = {u, v, w}; adj[u].push_back(i); adj[v].push_back(i); } dijkstra(0, a); dijkstra(1, b); dijkstra(2, c); dijkstra(3, d); for (int u = 1; u <= n; u++) { for (int i : adj[u]) { int v = edge[i].u ^ edge[i].v ^ u; if (dist[0][u] + dist[1][v] + edge[i].w == dist[0][b]) dag[u].push_back(v); } } topo(a); reverse(lst.begin(), lst.end()); for (int i = 1; i <= n; i++) dp[2][i] = dp[3][i] = -1; for (int u : lst) { minimize(dp[2][u], dist[2][u]); for (int v : dag[u]) minimize(dp[2][v], dp[2][u]); } for (int u : lst) { minimize(dp[3][u], dist[3][u]); for (int v : dag[u]) minimize(dp[3][v], dp[3][u]); } res = dist[2][d]; for (int i = 1; i <= n; i++) { if (dp[2][i] != -1) res = min(res, dp[2][i] + dist[3][i]); if (dp[3][i] != -1) res = min(res, dp[3][i] + dist[2][i]); } cout << res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...