제출 #690578

#제출 시각아이디문제언어결과실행 시간메모리
690578Paul_Liao_1457Olympic Bus (JOI20_ho_t4)C++17
0 / 100
218 ms3052 KiB
//記得跳題 #include<iostream> #include<array> #include<vector> #include<string> #include<algorithm> #include<set> #include<queue> #include<stack> #include<math.h> #include<map> #include<unordered_map> #include<cstring> #include<iomanip> #include<bitset> #include<tuple> #define ll long long #define LL __int128_t #define DB double #define FOR(i,a,b) for(int i=a;i<b;i++) #define REP(i,a,b) for(int i=a;i>=b;i--) #define pb push_back #define mp make_pair #define INF (ll)(1e9+2e8+5) #define MOD (ll)(1e9+7) #define F first #define S second #define endl "\n" #define AC ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; template<class T> using PQ=priority_queue<T,vector<T>,greater<T> >; void file(){ freopen("/Users/liaoyunyang/Desktop/meta_in.txt","r",stdin); freopen("/Users/liaoyunyang/Desktop/meta_out.txt","w",stdout); } bool used[2][50005],vis[205]; int dis[2][2][205]; int a[50005],b[50005],c[50005],d[50005],tmp[205]; vector<int> e[2][205]; signed main(){ AC; int n,m; cin>>n>>m; FOR(i,1,m+1){ cin>>a[i]>>b[i]>>c[i]>>d[i]; e[0][a[i]].pb(i); e[0][b[i]].pb(i+m); e[1][b[i]].pb(i); } FOR(x,0,2)FOR(y,0,2)FOR(i,0,n+1) dis[x][y][i]=INF; PQ<pair<int,pair<int,int> > > pq; pq.push({0,{1,0}}); while(pq.size()){ int t=pq.top().F,now=pq.top().S.F,id=pq.top().S.S; pq.pop(); if(dis[0][0][now]!=INF) continue; dis[0][0][now]=t; used[0][id]=1; for(auto i:e[0][now])if(i<=m){ pq.push({t+c[i],{b[i],i}}); } } pq.push({0,{n,0}}); while(pq.size()){ int t=pq.top().F,now=pq.top().S.F; pq.pop(); if(dis[0][1][now]!=INF) continue; dis[0][1][now]=t; for(auto i:e[1][now])if(i<=m){ pq.push({t+c[i],{a[i],i}}); } } pq.push({0,{n,0}}); while(pq.size()){ int t=pq.top().F,now=pq.top().S.F,id=pq.top().S.S; pq.pop(); if(dis[1][0][now]!=INF) continue; dis[1][0][now]=t; used[1][id]=1; for(auto i:e[0][now])if(i<=m){ pq.push({t+c[i],{b[i],i}}); } } pq.push({0,{1,0}}); while(pq.size()){ int t=pq.top().F,now=pq.top().S.F; pq.pop(); if(dis[1][1][now]!=INF) continue; dis[1][1][now]=t; for(auto i:e[1][now])if(i<=m){ pq.push({t+c[i],{a[i],i}}); } } ll ans=(ll)dis[0][0][n]+dis[1][0][1]; FOR(i,1,m+1){ //cout<<"ans="<<ans<<endl; ll d1=INF,d2=INF; if(used[0][i]){ FOR(j,0,n+1){ tmp[j]=INF; vis[j]=0; } int now=n+1; tmp[now]=INF; tmp[1]=0; FOR(x,0,n){ now=n+1; FOR(y,1,n+1)if(!vis[y]&&tmp[y]<tmp[now]){ now=y; } if(tmp[now]==INF){ d1=INF; break; } if(now==n) break; vis[now]=1; for(auto j:e[0][now])if(j!=i){ if(j<=m) tmp[b[j]]=min(tmp[b[j]],tmp[now]+c[j]); else if(j==i+m) tmp[a[i]]=min(tmp[a[i]],tmp[now]+c[i]); } } d1=tmp[n]; } else{ //cout<<"hi"<<endl; d1=min((ll)dis[0][0][n],(ll)dis[0][0][b[i]]+dis[0][1][a[i]]+c[i]); } if(used[1][i]){ FOR(j,0,n+1){ tmp[j]=INF; vis[j]=0; } int now=n+1; tmp[now]=INF; tmp[n]=0; FOR(x,1,n+1){ now=n+1; FOR(y,1,n+1)if(!vis[y]&&tmp[y]<tmp[now]){ now=y; } if(tmp[now]==INF){ d2=INF; break; } if(now==n) break; vis[now]=1; for(auto j:e[0][now])if(j!=i){ if(j<=m) tmp[b[j]]=min(tmp[b[j]],tmp[now]+c[j]); else if(j==i+m) tmp[a[i]]=min(tmp[a[i]],tmp[now]+c[i]); } } d2=tmp[1]; } else{ //cout<<"i="<<i<<endl; d2=min((ll)dis[1][0][1],(ll)dis[1][0][b[i]]+dis[1][1][a[i]]+c[i]); } //cout<<"d1="<<d1<<" d2="<<d2<<endl; ans=min((ll)ans,((ll)d1+(ll)d2+(ll)d[i])); } if(ans>=INF) cout<<"-1"<<endl; else cout<<ans<<endl; } /* 4 5 1 2 4 4 1 3 2 1 4 3 1 2 4 1 6 1 2 4 2 5 */

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

ho_t4.cpp: In function 'void file()':
ho_t4.cpp:37:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     freopen("/Users/liaoyunyang/Desktop/meta_in.txt","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ho_t4.cpp:38:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     freopen("/Users/liaoyunyang/Desktop/meta_out.txt","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...