제출 #76548

#제출 시각아이디문제언어결과실행 시간메모리
76548VasiljkoCommuter Pass (JOI18_commuter_pass)C++14
31 / 100
1051 ms22528 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll MOD = 1e9+7; const int N =1e5+5; const ll INF = 1e18; int n,m,T; bool vis[N]; ll du[N],dv[N],ds[N],dt[N],d1[N],d2[N],ans; vector<pair<int,ll> >v[2*N]; priority_queue<pair<ll,int> >pq; multiset<ll>su,sv; void Dijkstra(ll *d,int s){ for(int i=1;i<=N;i++)d[i]=INF; d[s]=0; pq.push({-d[s],s}); while(!pq.empty()){ auto cur=pq.top(); pq.pop(); for(auto e:v[cur.second]){ if(d[cur.second]+e.second<d[e.first]){ d[e.first]=d[cur.second]+e.second; pq.push({-d[e.first],e.first}); } } } } void dfs(int cur){ vis[cur]=true; su.insert(du[cur]); sv.insert(dv[cur]); for(auto e:v[cur]){ if(ds[cur]+e.second+dt[e.first]==ds[T]&&!vis[e.first]){//if e is part of shortest path dfs(e.first); } } } void solve(ll *d,ll *dd) { memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++)dd[i]=d[i],pq.push({-dd[i],i}); while(!pq.empty()) { int r = pq.top().second; pq.pop(); if(vis[r])continue; vis[r]=1; for(auto x:v[r]) { int u = x.first; int c = x.second; if(ds[r]+c+dt[u]==ds[T]){ if(dd[r]>dd[u]){ dd[r]=dd[u]; pq.push({-dd[r],r}); }else if(dd[r]<dd[u]){ dd[u]=dd[r]; pq.push({-dd[u],u}); } } } } } int main() { ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); int s,t,a,b,x,y,z; cin>>n>>m; cin>>s>>t; cin>>a>>b; T=t; for(int i=1;i<=m;i++){ cin>>x>>y>>z; v[x].push_back({y,z}); v[y].push_back({x,z}); } Dijkstra(du,a); Dijkstra(dv,b); Dijkstra(ds,s); Dijkstra(dt,t); solve(dv,d1); solve(du,d2); ans=INF; for(int i=1;i<=n;i++){ ans=min(ans,du[i]+d1[i]); ans=min(ans,dv[i]+d2[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...