제출 #1110991

#제출 시각아이디문제언어결과실행 시간메모리
1110991haianhnguyen08102007Commuter Pass (JOI18_commuter_pass)C++17
0 / 100
4 ms18768 KiB
#include<bits/stdc++.h> #define ll long long using namespace std; const int N=4e5+10; ll n,m,s,t,u,v,x[N],y[N],z[N],d1[N],d2[N],d3[N],d4[N],ans; struct graph { ll cnt,dis[N],head[N],in[N],mind[N],v[N],f[N]; struct Edge { ll nx,to,cost; }edg[N]; struct node { ll id,ans; bool operator < (const node &x)const { return x.ans<ans; } }; void add(int a,int b,int c) { edg[++cnt].to=b; edg[cnt].cost=c; edg[cnt].nx=head[a]; in[b]++; head[a]=cnt; } priority_queue<node> q; void dj(int s,ll dis[]) { for(int i=1;i<=n;i++)dis[i]=1ll*1e18; memset(v,0,sizeof(v)); dis[s]=0; q.push((node){s,0}); while(!q.empty()) { node temp=q.top(); q.pop(); ll u=temp.id; if(v[u])continue; v[u]=1; for(int j=head[u];j;j=edg[j].nx) { int to=edg[j].to; if(dis[to]>dis[u]+edg[j].cost) { dis[to]=dis[u]+edg[j].cost; if(!v[to])q.push((node){to,dis[to]}); } } } } void solve() { queue<int> q; for(int i=1;i<=n;i++) { mind[i]=d3[i]; if(!in[i])q.push(i); } while(!q.empty()) { int x=q.front();q.pop(); if(f[x])continue; f[x]=1; ans=min(ans,mind[x]+d4[x]); for(int j=head[x];j;j=edg[j].nx) { int v=edg[j].to; in[v]--;mind[v]=min(mind[v],mind[x]); if(!in[v])q.push(v); } } } }g1,g2,g3; int main() { ios::sync_with_stdio(0); freopen("COMMUTER.INP", "r", stdin); freopen("COMMUTER.OUT", "w", stdout); cin>>n>>m>>s>>t>>u>>v; for(int i=1;i<=m;i++) { cin>>x[i]>>y[i]>>z[i]; g1.add(x[i],y[i],z[i]); g1.add(y[i],x[i],z[i]); } g1.dj(s,d1);g1.dj(t,d2);g1.dj(u,d3);g1.dj(v,d4); ans=d3[v]; for(int i=1;i<=m;i++) { if(d1[x[i]]+z[i]+d2[y[i]]==d1[t])g2.add(x[i],y[i],0),g3.add(y[i],x[i],0); else if(d1[y[i]]+z[i]+d2[x[i]]==d1[t])g2.add(y[i],x[i],0),g3.add(x[i],y[i],0); } g2.solve();g3.solve(); cout<<ans<<'\n'; return 0; }

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

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:81:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |     freopen("COMMUTER.INP", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:82:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |     freopen("COMMUTER.OUT", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...