제출 #731630

#제출 시각아이디문제언어결과실행 시간메모리
731630khshgCommuter Pass (JOI18_commuter_pass)C++14
100 / 100
418 ms30896 KiB
#include <algorithm> #include <array> #include <bitset> #include <cassert> #include <chrono> #include <climits> #include <cmath> #include <complex> #include <cstring> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <numeric> #include <queue> #include <random> #include <set> #include <unordered_set> #include <vector> using namespace std; #define int long long using ll = long long; using ld = long double; using str = string; using pi = pair<int, int>; using pl = pair<ll, ll>; using pd = pair<ld, ld>; #define mp make_pair #define ff first #define ss second template<class T> using V = vector<T>; #define arr array using vi = V<int>; using vb = V<bool>; using vl = V<ll>; using vd = V<ld>; using vs = V<str>; using vpi = V<pi>; using vpl = V<pl>; using vpd = V<pd>; #define sz(x) (int)((x).size()) #define bg(x) begin(x) #define all(x) bg(x), end(x) #define rall(x) (x).rbegin(), (x).rend() #define sor(x) sort(all(x)) #define rsz resize #define ins insert #define pb push_back #define eb emplace_back #define ft front() #define bk back() #define lb lower_bound #define ub upper_bound #define FOR(i, a, b) for(int i = (a); i < (b); ++i) #define F0R(i, a) FOR(i, 0, a) #define ROF(i, a, b) for(int i = (b) - 1; i >= (a); --i) #define R0F(i, a) ROF(i, 0, a) #define rep(a) F0R(_, a) #define trav(a, x) for(auto& a : x) template<class T> bool ckmin(T& a, const T& b) { return (b < a ? a = b, 1 : 0); } template<class T> bool ckmax(T& a, const T& b) { return (b > a ? a = b, 1 : 0); } const ll INF = 0x3f3f3f3f3f3f3f3f; const int maxn = 100000; vpi adj[maxn]; vi par[maxn]; int N, M; int S, T; int U, Vv; ll ans; vl fromU, fromV; void dijkstra(int st, vl& dis) { dis = vl(N, INF); priority_queue<pl> pq; pq.push({dis[st] = 0, st}); while(sz(pq)) { ll D; int cur; tie(D, cur) = pq.top(); pq.pop(); D *= -1LL; if(dis[cur] < D) { continue; } trav(u, adj[cur]) { if(dis[u.ff] > D + u.ss) { pq.push({-(dis[u.ff] = D + u.ss), u.ff}); } } } } void dfs(int s, V<arr<ll, 2>>& dp) { dp[s][0] = fromU[s]; dp[s][1] = fromV[s]; trav(u, par[s]) { if(dp[u][0] == INF && dp[u][1] == INF) { dfs(u, dp); } ckmin(dp[s][0], dp[u][0]); ckmin(dp[s][1], dp[u][1]); } } V<arr<ll, 2>> pp(int st, int en) { vl dis(N, INF); priority_queue<pl> pq; pq.push({dis[st] = 0, st}); par[st].clear(); while(sz(pq)) { ll D; int cur; tie(D, cur) = pq.top(); pq.pop(); D *= -1LL; if(dis[cur] < D) { continue; } trav(u, adj[cur]) { if(dis[u.ff] > D + u.ss) { pq.push({-(dis[u.ff] = D + u.ss), u.ff}); par[u.ff].clear(); } if(dis[u.ff] == D + u.ss) par[u.ff].eb(cur); } } V<arr<ll, 2>> dp(N, arr<ll, 2>{INF, INF}); // 0 -> U; 1 -> V; dfs(en, dp); return dp; } int32_t main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> N >> M; cin >> S >> T; cin >> U >> Vv; --S; --T; --U; --Vv; rep(M) { int A, B, C; cin >> A >> B >> C; --A; --B; adj[A].eb(B, C); adj[B].eb(A, C); } dijkstra(U, fromU); dijkstra(Vv, fromV); ans = fromU[Vv]; V<arr<ll, 2>> fS = pp(S, T); V<arr<ll, 2>> fT = pp(T, S); F0R(i, N) { ckmin(ans, fS[i][0] + fT[i][1]); ckmin(ans, fS[i][1] + fT[i][0]); } cout << ans << '\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...