PKU 2982 Time Travel
http://poj.org/problem?id=2982
原点から座標(n,m)まで移動するのにかかるコストを求めろというような問題。
ただし、途中で原点と座標(n,m)で作れる長方形から出てはいけない。
ダイクストラしました。
好き勝手に移動していてTLEやらWAやらをもらいまくりました。
bool vis[110][10000]; int a[110],b[110],c[110]; int n,m,k; void solve(){ memset(vis,0,sizeof(vis)); rep(i,k) scanf("%d%d%d",a+i,b+i,c+i); priority_queue<pair<int,PI> >q; q.push(mp(0,mp(0,0))); //m+=5000; while(!q.empty()){ int cc=-q.top().F; int cx=q.top().S.F; int cy=q.top().S.S; q.pop(); if(cy<0 || cy>m)continue; for(;0 > cy || cy>=10000;); if(vis[cx][cy])continue; vis[cx][cy]=true; if(cx==n && cy==m){ cout<<cc<<endl; return; } rep(i,k) if(cx+a[i]<=n) q.push(mp(-cc-c[i],mp(cx+a[i],cy+b[i]))); } cout<<-1<<endl; } main(){ while(cin>>n>>m>>k,n|m|k) solve(); }