謎
PKU 2671なんだけど,while (1);を書くかどうかでACがWAになる.
ダイクストラで解いたのだけど,擬似コードはこんな感じ.
int bfs(){ while (!q.empty()){ } while (1); // これを消すとWA } int main(){ ... ... cout << bfs() << endl; }
なんぞこれ?
実際のコード
#include <iostream> #include <queue> #include <cstdio> using namespace std; int distsum[300][300]; int costsum[300][300]; int dist[300]; int cost[300]; int totaldist,totalcost; int dp[300][300][2]; int N; #define RIGHT 1 #define LEFT 0 struct State{ int left,right,which; int cost; bool operator<(const State& s)const{ return cost > s.cost; } }; int bfs(){ priority_queue<State> up; up.push((State){0,0,0,0}); up.push((State){0,0,1,0}); while (!up.empty()){ State st = up.top(); up.pop(); int l = st.left; int r = st.right; int c = st.cost; int w = st.which; //cout << l << " " << r << " " << c << " " << w << endl; if (c > dp[l][r][w]) continue; if ((r+1)%N==l) return c; int nl = (l + N - 1) % N; int nr = (r + 1) % N; int nc,nw; if (w == RIGHT){ nc = c + (totalcost - costsum[l][r])*distsum[nl][r]; nw = LEFT; if (dp[nl][r][nw] > nc){ up.push((State){nl,r,nw,nc}); dp[nl][r][nw] = nc; } nc = c + (totalcost - costsum[l][r])*distsum[r][nr]; nw = RIGHT; if (dp[l][nr][nw] > nc){ up.push((State){l,nr,nw,nc}); dp[l][nr][nw] = nc; } }else{ // from LEFT nc = c + (totalcost - costsum[l][r])*distsum[nl][l]; nw = LEFT; if (dp[nl][r][nw] > nc){ up.push((State){nl,r,nw,nc}); dp[nl][r][nw] = nc; } nc = c + (totalcost - costsum[l][r])*distsum[l][nr]; nw = RIGHT; if (dp[l][nr][nw] > nc){ up.push((State){l,nr,nw,nc}); dp[l][nr][nw] = nc; } } } while (1); // これを消すとWA } int main(){ while (1){ scanf("%d",&N); if (!N) break; totaldist = 0; totalcost = 0; for (int i=0;i<N;i++){ scanf("%d%d",&cost[i],&dist[i]); totalcost += cost[i]; totaldist += dist[i]; } for (int i=0;i<N;i++) for (int j=0;j<N;j++) for (int k=0;k<2;k++) dp[i][j][k] = 1 << 30; for (int i=0;i<N;i++){ int dsum=0,csum=0; for (int j=i;;j++){ j %= N; csum += cost[j]; costsum[i][j] = csum; distsum[i][j] = dsum; dsum += dist[j]; if ((j+1)%N==i) break; } } cout << bfs() << endl; } }
なんぞこれ?
追記
intの関数が値を返した方がいいというのはまさにそのとおりでございます.
でもwhile(1)