제출 #814769

#제출 시각아이디문제언어결과실행 시간메모리
814769akariCommuter Pass (JOI18_commuter_pass)C++17
16 / 100
485 ms21828 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define fi first #define se second #define ii pair<ll,ll> const ll maxn=1e5+7,inf=1e16; int n,m,s,t,op,ed; vector<ll> d1,d2,t1,t2; vector<ii> adj[maxn]; vector<ll> g[maxn]; vector<int> ver; bool ok[maxn]; bool pass[maxn]; ll ans=inf; ll dp[maxn],pd[maxn]; int p[maxn]; void dij(int st, vector<ll> &dis){ dis.resize(n+9,inf); priority_queue <ii,vector<ii>,greater<ii>> pq; pq.push({0,st}); dis[st]=0; while(!pq.empty()){ int u=pq.top().se; int d=pq.top().fi; pq.pop(); if (dis[u]<d) continue; for (ii v:adj[u]){ if (dis[v.fi]>dis[u]+v.se){ dis[v.fi]=dis[u]+v.se; pq.push({dis[v.fi],v.fi}); } } } } void dfs(int u){ if (pass[u]) return; pass[u]=1; //cout<<u<<endl; for (ii i: adj[u]){ int v=i.fi; if (ok[v]==0) continue; if (d1[u]+d2[v]+i.se==d1[t]){ dp[v]=min(dp[v],dp[u]); pd[v]=min(pd[v],pd[u]); } dfs(v); } } int main(){ cin>>n>>m>>s>>t>>op>>ed; while (m--){ int a,b,c; cin>>a>>b>>c; adj[a].push_back({b,c}); adj[b].push_back({a,c}); } dij(s,d1); dij(t,d2); dij(op,t1); dij(ed,t2); for (int i=1;i<=n;++i){ dp[i]=t1[i]; pd[i]=t2[i]; if (d1[i]+d2[i] == d1[t]){ ver.push_back(i); ok[i]=1; } } //dfs(t); if (s==op){ for (int i:ver){ ans=min(ans,t2[i]); } cout<<ans; return 0; } /*ll sna=inf; for (int i:ver){ ans=min(ans,t1[i]); sna=min(sna,t2[i]); } cout<<min(ans+sna,t1[ed]); return 0;*/ /*for (int i: ver){ for (ii x: adj[i]) if (ok[x.fi]) g[i].push_back(x.fi); }*/ /* /*queue<ii> qu; qu.push({s,s}); pass[s]=1; while (!qu.empty()){ int u=qu.front().fi; int p=qu.front().se; //cout<<u<<endl; qu.pop(); dp[u]=min(dp[p],t2[u]); for (int v: g[u]){ dp[v]=min(dp[u],t2[v]); if (pass[v]==0){ pass[v]=1; qu.push({v,u}); } } }*/ /*pass[s]=1; for (int i: ver){ while (pass[i]==0){ //cout<<i<<" "; for (int v: g[i]){ if (!ok[v]) continue; dp[i]=min(dp[i],dp[v]); pd[i]=min(pd[i],pd[v]); } pass[i]=1; dp[i]=min(dp[i],dp[p[i]]); pd[i]=min(pd[i],pd[p[i]]); i=p[i]; } //cout<<i<<" i\n"; } /*for (int i: ver){ for (int j: g[i]) cout<<j<<" "; cout<<i<<endl; }*/ dfs(s); for (int u:ver) ans=min(ans,t2[u]+dp[u]); for (int v:ver) ans=min(ans,t1[v]+pd[v]); //for (int i:ver) cout<<i<<" "<<p[i]<<endl; cout<<min(ans,t1[ed]); }

컴파일 시 표준 에러 (stderr) 메시지

commuter_pass.cpp:92:5: warning: "/*" within comment [-Wcomment]
   92 |     /*queue<ii> qu;
      |      
commuter_pass.cpp:126:5: warning: "/*" within comment [-Wcomment]
  126 |     /*for (int i: ver){
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...