Submission #226470

#TimeUsernameProblemLanguageResultExecution timeMemory
226470thebesOlympic Bus (JOI20_ho_t4)C++14
0 / 100
401 ms162224 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef vector<int> vi; #define pb push_back const int MN = 202, MM = 5e4+5; int N, M, i, j, x, y, w[MM], c[MM], u[MM], vs[MN], ban[MM], par[MN]; ll ans, dis[MN], a[MM][MN], b[MM][MN], cost[MM]; vector<pii> adj[MN], rev[MN]; vi tree; pii ed[MM]; queue<int> q; int st[MN]; void dij(int src,bool dir){ q.push(src); memset(par,-1,sizeof(par)); for(i=1;i<=N;i++) dis[i]=1LL<<55; dis[src]=0; while(q.size()){ int cur=q.front(); q.pop(); if(vs[cur]) continue; st[cur]=0; if(dir==1){ for(auto v : adj[cur]){ if(ban[v.second]) continue; if(dis[cur]+w[v.second]<dis[v.first]){ dis[v.first]=dis[cur]+w[v.second]; par[v.first]=v.second; if(!st[v.first]){ st[v.first]=1; q.push(v.first); } } } } else{ for(auto v : rev[cur]){ if(ban[v.second]) continue; if(dis[cur]+w[v.second]<dis[v.first]){ dis[v.first]=dis[cur]+w[v.second]; par[v.first]=v.second; if(!st[v.first]){ st[v.first]=1; q.push(v.first); } } } } } for(i=1;i<=N;i++){ if(par[i]!=-1) u[par[i]]=1; } } int main(){ for(scanf("%d%d",&N,&M),i=1;i<=M;i++){ scanf("%d%d%d%d",&x,&y,&w[i],&c[i]); ed[i]={x,y}; adj[x].pb({y,i}); rev[y].pb({x,i}); } for(int k=0;k<2;k++){ memset(u,0,sizeof(u)); dij(1,1^k); tree.clear(); for(i=1;i<=M;i++){ if(u[i]) tree.pb(i); else{ for(j=1;j<=N;j++) a[i][j]=dis[j]; } } assert(tree.size()<=N); for(auto v : tree){ ban[v]=1; dij(1,1^k); for(j=1;j<=N;j++) a[v][j]=dis[j]; ban[v]=0; } memset(u,0,sizeof(u)); dij(N,k); tree.clear(); for(i=1;i<=M;i++){ if(u[i]) tree.pb(i); else{ for(j=1;j<=N;j++) b[i][j]=dis[j]; } } assert(tree.size()<=N); for(auto v : tree){ ban[v]=1; dij(N,k); for(j=1;j<=N;j++) b[v][j]=dis[j]; ban[v]=0; } for(j=1;j<=M;j++){ if(!k) cost[j]+=min(a[j][N],a[j][ed[j].second]+w[j]+b[j][ed[j].first]); else cost[j]+=min(a[j][N],a[j][ed[j].first]+w[j]+b[j][ed[j].second]); } } dij(1,1); ans+=dis[N]; dij(N,0); ans+=dis[1]; for(j=1;j<=M;j++) ans=min(ans,cost[j]+c[j]); if(ans>(1LL<<55)) printf("-1\n"); else printf("%lld\n",ans); return 0; }

Compilation message (stderr)

In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from ho_t4.cpp:1:
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:77:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         assert(tree.size()<=N);
                ~~~~~~~~~~~^~~
ho_t4.cpp:95:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         assert(tree.size()<=N);
                ~~~~~~~~~~~^~~
ho_t4.cpp:60:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(scanf("%d%d",&N,&M),i=1;i<=M;i++){
         ~~~~~~~~~~~~~~~~~~~^~~~
ho_t4.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d%d",&x,&y,&w[i],&c[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...