제출 #1038254

#제출 시각아이디문제언어결과실행 시간메모리
1038254Mike_VuCommuter Pass (JOI18_commuter_pass)C++14
100 / 100
242 ms33036 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef double dou; #define pii pair<int, ll> #define pb push_back #define fi first #define se second bool maximize(ll &x, ll y ){ if (x < y) {x = y; return true;}; return false; } bool minimize(ll &x, ll y){ if (x > y) {x = y; return true;} return false; } const int maxn = 1e5+5; int n, m, s1, t1, s2, t2; vector<pii> a[maxn]; ll ans; ll dis1[maxn], dis2[maxn], dis3[maxn], dis4[maxn];//dis1 dis2 -> s2 t2 ll dp1[maxn], dp2[maxn]; vector<int> adj[maxn]; int deg[maxn]; bool vis[maxn]; void dijkstra(int s, ll dis[]) { priority_queue<pair<ll, int>> q; q.push({0, s}); // memset(dis, 0x3f, sizeof(dis)); for (int i = 1; i <= n; i++) { dis[i] = LLONG_MAX; } dis[s] = 0; while (!q.empty()) { int u = q.top().se; ll w = -q.top().fi; q.pop(); if (w != dis[u]) continue; // cout << u << ' ' << dis[u] << "\n"; for (int i = 0; i < (int)a[u].size(); i++) { int v = a[u][i].fi; ll w = a[u][i].se; if (minimize(dis[v], dis[u]+w)) { q.push({-dis[v], v}); } } } } void dfs1(int u) { vis[u] = 1; for (int i = 0; i < (int)a[u].size(); i++) { int v = a[u][i].fi; ll w = a[u][i].se; if (dis3[u]+w+dis4[v] == dis3[t1]) { adj[u].pb(v); deg[v]++; } if (!vis[v]) dfs1(v); } } void bfs() { queue<int> q; q.push(s1); memset(dp1, 0x3f, sizeof(dp1)); memset(dp2, 0x3f, sizeof(dp2)); while (!q.empty()) { int u = q.front(); q.pop(); minimize(dp1[u], dis1[u]); minimize(dp2[u], dis2[u]); minimize(ans, min(dp1[u]+dis2[u], dp2[u]+dis1[u])); // cout << u << ' ' << dp1[u] << ' ' << dp2[u] << "\n"; for (int v : adj[u]) { deg[v]--; minimize(dp1[v], dp1[u]); minimize(dp2[v], dp2[u]); if (deg[v] == 0) q.push(v); } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); // cout << "\n"; cin >> n >> m >> s1 >> t1 >> s2 >> t2; for (int i = 1; i <= m; i++) { int u, v; ll w; cin >> u >> v >> w; a[u].pb({v, w}); a[v].pb({u, w}); } //dijkstra s2->t2 // system("pause"); dijkstra(s2, dis1); dijkstra(t2, dis2); // for (int i = 1; i <= n; i++) { // cout << dis1[i] << ' '; // } // cout << "\n"; //build dijkstra s1->t1 dijkstra(s1, dis3); dijkstra(t1, dis4); ans = dis1[t2]; //build edges // system("pause"); dfs1(s1); //bfs // system("pause"); bfs(); cout << ans; } /* 6 6 1 6 1 4 1 2 1 2 3 1 3 5 1 2 4 3 4 5 2 5 6 1 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...