JOI惨敗日誌2
こんにちはつよっしーというものです。約1年ぶりにJOIの記事を書きます。結果は無惨に予選落ちでした。
誤読はするし、緊張で頭は回らず散々でしたね。まぁ、感想はのちほど書きます。
1問目・・・はい
2問目・・・誤読
3問目・・・はい
4問目・・・bitDPと終ってから分かった
5問目・・・座標でDPみたいなことするらしい(???)
6問目・・・拡張ダイクストラ
1~3はあれでしたが、4~6の中で一番解けそうな6が解けずに終わって予選落ちしたのが悲しい(2を誤読して4ケース落としてたのでどっちにしろ予選落ち)
6問目は答えの配列を1次元にしてたのでバグってた(悲しい)。一応予選終わった後に解いた6のコードをあげます。
#include<bits/stdc++.h> #define int long long #define PB push_back #define MP make_pair #define FI first #define SE second using namespace std; static const int INF = 1ll<<60; static const int dx[] = {0,0,1,-1}; static const int dy[] = {1,-1,0,0}; typedef pair< int,int > PII; typedef pair< int,pair<int,int> > PPII; typedef pair< int,pair<int,pair<int, int> > > PPPII; struct edge{ int to,cost; edge(){} edge(int p1,int p2){ to=p1; cost=p2; } }; vector<edge> G[10005]; int dist[10005][205][5]; int A[20005]; int N,M,X; void dijkstra(int s){ priority_queue<PPPII,vector<PPPII>,greater<PPPII> > que; for(int i=0;i<10005;++i)for(int j=0;j<=200;++j)for(int k=0;k<3;++k)dist[i][j][k]=INF; dist[s][0][A[s]]=0; que.push(PPPII(0,PPII(s,PII(0,A[s])))); while(!que.empty()){ PPPII p = que.top(); que.pop(); int v=p.second.first; int time=p.second.second.first; int hot=p.second.second.second; if(dist[v][time][hot]<p.first)continue; for(int i=0;i<G[v].size();i++){ edge e = G[v][i]; int ntime,nhot; if(A[e.to]==0){ if(hot==2){ if(time+e.cost<X)continue; else { ntime=0; nhot=A[e.to]; if(dist[e.to][ntime][nhot]>dist[v][time][hot]+e.cost){ dist[e.to][ntime][nhot] = dist[v][time][hot]+e.cost; que.push(PPPII(dist[e.to][ntime][nhot],PPII(e.to,PII(ntime,nhot)))); } } } if(hot==0){ ntime=0; nhot=A[e.to]; if(dist[e.to][ntime][nhot]>dist[v][time][hot]+e.cost){ dist[e.to][ntime][nhot] = dist[v][time][hot]+e.cost; que.push(PPPII(dist[e.to][ntime][nhot],PPII(e.to,PII(ntime,nhot)))); } } } else if(A[e.to]==2){ if(hot==0){ if(time+e.cost<X)continue; else { ntime=0; nhot=A[e.to]; if(dist[e.to][ntime][nhot]>dist[v][time][hot]+e.cost){ dist[e.to][ntime][nhot] = dist[v][time][hot]+e.cost; que.push(PPPII(dist[e.to][ntime][nhot],PPII(e.to,PII(ntime,nhot)))); } } } if(hot==2){ ntime=0; nhot=A[e.to]; if(dist[e.to][ntime][nhot]>dist[v][time][hot]+e.cost){ dist[e.to][ntime][nhot] = dist[v][time][hot]+e.cost; que.push(PPPII(dist[e.to][ntime][nhot],PPII(e.to,PII(ntime,nhot)))); } } } else if(A[e.to]==1){ ntime=time+e.cost; nhot=hot; if(ntime>=X)ntime=200; if(dist[e.to][ntime][nhot]>dist[v][time][hot]+e.cost){ dist[e.to][ntime][nhot] = dist[v][time][hot]+e.cost; que.push(PPPII(dist[e.to][ntime][nhot],PPII(e.to,PII(ntime,nhot)))); } } } } } signed main(){ cin>>N>>M>>X; for(int i=0;i<N;++i)cin>>A[i]; for(int i=0;i<M;++i){ int a,b,c; cin>>a>>b>>c; a--; b--; G[a].PB(edge(b,c)); G[b].PB(edge(a,c)); } dijkstra(0); int ans=INF; for(int i=0;i<=200;++i){ for(int j=0;j<3;++j){ ans=min(ans,dist[N-1][i][j]); } } cout<<ans<<endl; return 0; }
JOIの感想なんですが実力を十分に発揮できず悔しさが残りました。自分が本番に弱いのとコンテスト慣れしてなかったのが原因ですね。
これからについてなんですが競プロはJOIだけではないのでPCKやICPCに向けてこれまで以上に精進したいと思います。
あと、Imagine Capについてなんですが特に書くことが思いつかなかったので予選が終わったころにでも書きたいと思います。
お通夜みたいな記事になってしまいましたがJOIは@kuro_koji_と@_izrytと@gedorinkuの三人が僕の無念を晴らしてIOI代表になってくれるので応援しています。
次回は@Fukusan64です。