제출 #211332

#제출 시각아이디문제언어결과실행 시간메모리
211332kshitij_sodaniOlympic Bus (JOI20_ho_t4)C++17
0 / 100
50 ms6272 KiB
#include <iostream> #include <bits/stdc++.h> using namespace std; typedef int64_t llo; #define mp make_pair #define pb push_back #define a first #define b second vector<pair<llo,llo>> adj[201]; vector<llo> cost[201]; vector<pair<llo,pair<llo,llo>>> adj2[201]; vector<pair<llo,pair<llo,llo>>> adj3[201]; llo dis[201][201]; llo vis[201]; llo vis2[201]; llo dp[201]; llo dp2[201]; vector<pair<pair<llo,llo>,pair<llo,llo>>> ed; map<pair<pair<llo,llo>,pair<llo,llo>>,llo> tt; llo dfs(llo no,llo par=-1,llo po=-1,llo po2=-1){ vis[no]=1; for(auto nn:adj2[no]){ if(vis[nn.a]==0){ dfs(nn.a,no,nn.b.a,nn.b.b); dp[no]+=dp[nn.a]; } else{ dp[no]+=1; dp[nn.a]-=1; } } if(dp[no]==0){ if(par>-1){ ed.pb({{par,no},{po,po2}}); tt[{{par,no},{po,po2}}]=1; } } } llo dfs2(llo no,llo par=-1,llo po=-1,llo po2=-1){ vis2[no]=1; for(auto nn:adj3[no]){ if(vis2[nn.a]==0){ dfs2(nn.a,no,nn.b.a,nn.b.b); dp2[no]+=dp2[nn.a]; } else{ dp2[no]+=1; dp2[nn.a]-=1; } } if(dp2[no]==0){ if(par>-1){ ed.pb({{par,no},{po,po2}}); tt[{{par,no},{po,po2}}]=1; } } } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); llo n,m; memset(dis,-1,sizeof(dis)); memset(vis,0,sizeof(vis)); memset(vis2,0,sizeof(vis2)); memset(dp,0,sizeof(dp)); memset(dp2,0,sizeof(dp2)); cin>>n>>m; llo ac,bb,cc,dd; // vector<pair<pair<llo,llo>,pair<llo,llo>>> ed; // llo kk=1; for(llo i=0;i<m;i++){ cin>>ac>>bb>>cc>>dd; adj[ac-1].pb({bb-1,cc}); cost[ac-1].pb(dd); if(dis[ac-1][bb-1]==-1){ dis[ac-1][bb-1]=cc; } dis[ac-1][bb-1]=min(dis[ac-1][bb-1],cc); } for(llo i=0;i<n;i++){ dis[i][i]=0; } for(llo k=0;k<n;k++){ for(llo i=0;i<n;i++){ for(llo j=0;j<n;j++){ if(dis[i][k]!=-1 and dis[k][j]!=-1){ if(dis[i][j]==-1){ dis[i][j]=dis[i][k]+dis[k][j]; } else{ dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); } } } } } llo indd=0; llo indd2=0; for(llo i=0;i<n;i++){ llo k=0; for(auto j:adj[i]){ if(dis[0][i]>-1 and dis[j.a][n-1]>-1){ if(dis[0][i]+dis[j.a][n-1]+j.b==dis[0][n-1]){ adj2[i].pb({j.a,{j.b,cost[i][k]}}); indd=j.a; // cout<<j.a<<" "<<i<<endl; } } if(dis[n-1][i]>-1 and dis[j.a][0]>-1){ if(dis[n-1][i]+dis[j.a][0]+j.b==dis[n-1][0]){ adj3[i].pb({j.a,{j.b,cost[i][k]}}); indd2=j.a; // cout<<j.a<<","<<i<<endl; } } k+=1; } } dfs(0); dfs2(n-1); llo ans=-1; if(dis[0][n-1]>-1 and dis[n-1][0]>-1){ ans=dis[0][n-1]+dis[n-1][0]; } /* for(llo i=0;i<ed.size();i++){ cout<<ed[i].a.a<<","<<ed[i].a.b<<" "<<ed[i].b.a<<" "<<ed[i].b.b<<endl; }*/ for(llo i=0;i<n;i++){ for(llo j=0;j<adj[i].size();j++){ llo nn=adj[i][j].a; // cout<<i<<" "<<nn<<" "<<adj[i][j].b<<" "<<cost[i][j]<<endl; if(tt.find({{i,nn},{adj[i][j].b,cost[i][j]}})==tt.end()){ if(dis[i][0]>-1 and dis[0][n-1]>-1 and dis[n-1][nn]>-1){ if(ans==-1){ ans=dis[i][0]+cost[i][j]+dis[n-1][nn]+dis[0][n-1]+adj[i][j].b; } ans=min(ans,dis[i][0]+cost[i][j]+dis[n-1][nn]+dis[0][n-1]+adj[i][j].b); } if(dis[i][n-1]>-1 and dis[n-1][0]>-1 and dis[0][nn]>-1){ if(ans==-1){ ans=dis[i][n-1]+cost[i][j]+dis[0][nn]+dis[n-1][0]+adj[i][j].b; } ans=min(ans,dis[i][n-1]+cost[i][j]+dis[0][nn]+dis[n-1][0]+adj[i][j].b); } if(dis[0][nn]>-1 and dis[n-1][nn]>-1 and dis[i][0]>-1 and dis[i][n-1]>0){ if(ans==-1){ ans=dis[0][nn]+dis[n-1][nn]+dis[i][0]+dis[i][n-1]+adj[i][j].b*2+cost[i][j]; } ans=min(ans,dis[0][nn]+dis[n-1][nn]+dis[i][0]+dis[i][n-1]+adj[i][j].b*2+cost[i][j]); } } else{ priority_queue<pair<llo,llo>> cc; llo dist[n]; for(llo i=0;i<n;i++){ dist[i]=-1; } dist[0]; cc.push({0,0}); while(!cc.empty()){ pair<llo,llo> bb=cc.top(); cc.pop(); bb.a=-bb.a; // cout<<bb.b<<" "<<bb.a<<endl; for(auto jj:adj[bb.b]){ if(dist[jj.a]==-1 or dist[jj.a]>bb.a+jj.b ){ if(bb.b!=i or jj.a!=nn){ dist[jj.a]=bb.a+jj.b; cc.push({-dist[jj.a],jj.a}); } } } if(bb.b==nn){ if(dist[i]==-1 or dist[i]>dist[bb.b]+adj[i][j].b){ dist[i]=dist[bb.b]+adj[i][j].b; cc.push({-dist[i],i}); } } } // cout<<dist[n-1]<<endl; llo dist2[n]; for(llo i=0;i<n;i++){ dist2[i]=-1; } dist2[0]; cc.push({0,0}); while(!cc.empty()){ pair<llo,llo> bb=cc.top(); cc.pop(); bb.a=-bb.a; for(auto jj:adj[bb.b]){ if(dist2[jj.a]==-1 or dist2[jj.a]>bb.a+jj.b ){ if(bb.b!=i or jj.a!=nn){ dist2[jj.a]=bb.a+jj.b; cc.push({-dist2[jj.a],jj.a}); } } } if(bb.b==nn){ if(dist2[i]==-1 or dist2[i]>dist2[bb.b]+adj[i][j].b){ dist2[i]=dist2[bb.a]+adj[i][j].b; cc.push({-dist2[i],i}); } } } // cout<<dist2[0]<<endl; if(dist[n-1]>-1 and dist2[0]>-1){ if(ans==-1){ ans=dist[n-1]+dist2[0]+cost[i][j]; } ans=min(ans,dist[n-1]+dist2[0]+cost[i][j]); } } } } cout<<ans<<endl; return 0; }

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

ho_t4.cpp: In function 'llo dfs(llo, llo, llo, llo)':
ho_t4.cpp:39:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
ho_t4.cpp: In function 'llo dfs2(llo, llo, llo, llo)':
ho_t4.cpp:58:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:136:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(llo j=0;j<adj[i].size();j++){
               ~^~~~~~~~~~~~~~
ho_t4.cpp:167:11: warning: statement has no effect [-Wunused-value]
     dist[0];
     ~~~~~~^
ho_t4.cpp:195:12: warning: statement has no effect [-Wunused-value]
     dist2[0];
     ~~~~~~~^
ho_t4.cpp:102:6: warning: variable 'indd' set but not used [-Wunused-but-set-variable]
  llo indd=0;
      ^~~~
ho_t4.cpp:103:6: warning: variable 'indd2' set but not used [-Wunused-but-set-variable]
  llo indd2=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...