제출 #769428

#제출 시각아이디문제언어결과실행 시간메모리
769428AloraCommuter Pass (JOI18_commuter_pass)C++17
55 / 100
291 ms26484 KiB
#include <bits/stdc++.h> #define name "cownav" #define fi(i,a,b) for(int i = a; i <= b; i++) #define fid(i,a,b) for(int i = a; i >= b; i--) #define ll long long #define int long long #define f first #define se second #define pii pair<ll, int> #define getbit(i, j) ((i >> j) & 1) #define pb push_back #define all(v) v.begin(), v.end() #define maxn 200005 const int M = 1e9 + 7; using namespace std; int n, m, S, T, U, V; vector <pii> g[maxn]; vector <vector<ll>> dp(5, vector<ll>(maxn, 1e18)); void dij(int x, vector <ll> &L){ L[x] = 0; priority_queue <pii> q; q.push({0, x}); while(q.size()){ ll h = -q.top().f; int u = q.top().se; q.pop(); if(h != L[u]) continue; for(auto e: g[u]){ int v = e.f, w = e.se; if(L[v] > L[u] + w){ L[v] = L[u] + w; q.push({-L[v], v}); } } } } ll L[303][303]; bool check(int u, int v){ if(L[u][S] + L[u][v] + L[v][T] == L[S][T]) return 1; if(L[v][S] + L[u][v] + L[u][T] == L[S][T]) return 1; return 0; } void sub3(){ fi(i, 1, n) fi(j, 1, n) L[i][j] = 1e18; fi(i, 1, n) L[i][i] = 0; fi(i, 1, m){ int u, v, z; cin >> u >> v >> z; L[u][v] = L[v][u] = z; } fi(k, 1, n) fi(i, 1, n) fi(j, 1, n) L[i][j] = min(L[i][j], L[i][k] + L[k][j]); ll res = L[U][V]; fi(i, 1, n) fi(j, 1, n)if(check(i, j)){ res = min({res, L[U][i] + L[j][V], L[U][j] + L[i][V]}); } cout << res; exit(0); } signed main(){ ios_base::sync_with_stdio(0); cin.tie(NULL); // freopen(name".in", "r", stdin); /// freopen(name".out", "w", stdout); cin >> n >> m; cin >> S >> T >> U >> V; if(n <= 300) sub3(); fi(i, 1, m){ int u, v, z; cin >> u >> v >> z; g[u].pb({v, z}); g[v].pb({u, z}); } dij(S, dp[0]); dij(T, dp[1]); dij(U, dp[2]); dij(V, dp[3]); ll d1 = 1e18, d2 = 1e18; fi(i, 1, n) if(dp[0][i] + dp[1][i] == dp[0][T]){ d1 = min(d1, dp[2][i]); d2 = min(d2, dp[3][i]); } cout << min(d1 + d2, dp[2][V]); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...