제출 #1085198

#제출 시각아이디문제언어결과실행 시간메모리
1085198DucNguyen2007Commuter Pass (JOI18_commuter_pass)C++14
100 / 100
205 ms38224 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define pll pair<ll,ll> #define fi first #define se second const int maxN=2e5+5; const ll inf=2e18; int n,m,a,b,c,d; struct duongdi { int u; ll w; bool operator < (const duongdi &o)const { return w>o.w; } }; struct canh { int u,v; ll w; }p[maxN+1]; priority_queue<duongdi> pq; ll dist[4][maxN+1],dp1[maxN+1],dp2[maxN+1]; bool vis[maxN+1]; vector<duongdi> adj[maxN+1]; vector<int> dadj[maxN+1],topo; void dijkstra(int x,int type) { for(int i=1;i<=n;i++) { dist[type][i]=inf; } dist[type][x]=0; pq.push({x,0}); //cout<<x<<" "<<cd(x)<<'\n'; x=type; while(!pq.empty()) { duongdi tmp=pq.top(); pq.pop(); int u=tmp.u; ll w=tmp.w; if(dist[x][u]<w) { continue; } for(auto i:adj[u]) { int v=i.u; if(dist[x][v]>dist[x][u]+i.w) { dist[x][v]=dist[x][u]+i.w; pq.push({v,dist[x][v]}); } } } } void dfs(int u) { vis[u]=true; for(auto v:dadj[u]) { if(!vis[v]) { dfs(v); } } topo.push_back(u); } int main() { //freopen("","r",stdin); //freopen("","w",stdout); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m>>a>>b>>c>>d; for(int i=1;i<=m;i++) { int u,v; ll w; cin>>u>>v>>w; p[i].u=u; p[i].v=v; p[i].w=w; adj[u].push_back({v,w}); adj[v].push_back({u,w}); } dijkstra(a,0); dijkstra(b,1); dijkstra(c,2); dijkstra(d,3); for(int i=1;i<=m;i++) { int u=p[i].u,v=p[i].v; ll w=p[i].w; if(dist[0][u]+w+dist[1][v]==dist[0][b]) { dadj[u].push_back(v); //cout<<u<<" "<<v<<'\n'; } else if(dist[0][v]+w+dist[1][u]==dist[0][b]) { dadj[v].push_back(u); } } memset(vis,false,sizeof(vis)); dfs(a); reverse(topo.begin(),topo.end()); for(int i=1;i<=n;i++) { dp1[i]=dp2[i]=inf; } for(auto u:topo) { dp1[u]=min(dp1[u],dist[2][u]); dp2[u]=min(dp2[u],dist[3][u]); //cout<<u<<'\n'; for(auto v:dadj[u]) { dp1[v]=min(dp1[v],dp1[u]); dp2[v]=min(dp2[v],dp2[u]); //cout<<v<<" "<<dp1[v]<<" "<<dp1[u]<<'\n'; } } //cout<<'\n'; ll ans=dist[2][d]; // cout<<ans<<'\n'; for(int i=1;i<=n;i++) { ans=min(ans,min(dp1[i]+dist[3][i],dp2[i]+dist[2][i])); //cout<<i<<" "<<dp1[i]<<" "<<dp2[i]<<'\n'; } cout<<ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...