제출 #680543

#제출 시각아이디문제언어결과실행 시간메모리
680543viciousCommuter Pass (JOI18_commuter_pass)C++17
15 / 100
433 ms27012 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define fi first #define si second typedef pair<ll,int> pi; typedef tuple<int,int,int> ti; template<typename T> bool chmin(T &a, T b){return (b < a) ? a = b, 1 : 0;} template<typename T> bool chmax(T &a, T b){return (b > a) ? a = b, 1 : 0;} void debug_out() {cerr<<endl;} template <typename Head, typename... Tail> void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);} #define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__) const int N = 100010; const ll oo = 1e18; int n,m,S,T,U,V; vector<pi> g[N],par[N]; int vis[N]; vector<ll> ds,dt,du,dv,dp1,dp2; void sp(int src, vector<ll>& dist) { priority_queue<pi,vector<pi>,greater<pi>>q; dist.resize(n+1,-1); dist[src]=0; q.push({0,src}); for (int i = 1; i <= n; ++i) par[i].clear(); while (q.size()) { auto [d,x] = q.top(); q.pop(); if (dist[x]!=d) continue; for (auto i: g[x]) { ll nd = i.si+d; if (dist[i.fi]==-1||dist[i.fi]>nd) { dist[i.fi]=nd; par[i.fi].clear(); par[i.fi].push_back({x,i.si}); q.push({nd,i.fi}); } else if (dist[i.fi]==nd) { par[i.fi].push_back({x,i.si}); } } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin.exceptions(ios::badbit|ios::failbit); cin>>n>>m>>S>>T>>U>>V; for (int i = 1; i <= m; ++i) { int u,v,c; cin >>u>>v>>c; g[u].push_back({v,c}); g[v].push_back({u,c}); } sp(U,du);sp(V,dv);sp(S,ds); dp1.resize(n+1,oo), dp2.resize(n+1,oo); queue<int> q; q.push(T); vis[T]=1; dp1[V]=0; dp1[T]=dv[T]; while (q.size()) { int x = q.front(); q.pop(); for (auto v: par[x]) { if (vis[v.fi]) continue; vis[v.fi]=1; chmin(dp1[v.fi], dp1[x]); chmin(dp1[v.fi], dv[v.fi]); q.push(v.fi); } } memset(vis,0,sizeof vis); sp(T,dt); q.push(S); vis[S]=1; dp2[V]=0; dp2[S]=dv[S]; while (q.size()) { int x = q.front(); q.pop(); for (auto v: par[x]) { if (vis[v.fi]) continue; vis[v.fi]=1; chmin(dp2[v.fi], dp2[x]); chmin(dp2[v.fi], dv[v.fi]); q.push(v.fi); } } ll ans = du[V]; for (int i = 1; i <= n; ++i) { if (vis[i]) { chmin(ans, du[i]+min(dp1[i],dp2[i])); } } cout << ans; 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...