PKU 1695 Magazine Delivery
http://poj.org/problem?id=1695
3台の車を使ってN個の点を小さいほうから順番に通過していくために必要な最短コストを答えろというような問題。
3台の車の位置を保持してダイクストラしました。
車が戻る場合も考えたらWAになったので、いまいちこのアルゴリズムに自信が持てません。
bool vis[30][30][30]; typedef struct _state{ int pos[3]; int cc; bool operator<(const _state &r )const{ return r.cc<cc; } }state; int cost[30][30]; void solv(){ memset(vis,0,sizeof(vis)); memset(cost,0,sizeof(cost)); int n; cin>>n; rep(i,n-1){ for(int j=i+1;j<n;++j){ cin>>cost[i][j]; cost[j][i]=cost[i][j]; } } priority_queue<state> q; q.push((state){0,0,0,0}); while(!q.empty()){ state cst=q.top(); q.pop(); if(vis[cst.pos[0]][cst.pos[1]][cst.pos[2]])continue; vis[cst.pos[0]][cst.pos[1]][cst.pos[2]]=true; int maxi=*max_element(cst.pos,cst.pos+3); if(maxi==n-1){ cout<<cst.cc<<endl; break; } rep(i,3){ state nst=cst; nst.pos[i]=maxi+1; if(vis[nst.pos[0]][nst.pos[1]][nst.pos[2]])continue; nst.cc+=cost[cst.pos[i]][maxi+1]; q.push(nst); } } } main(){ int m; cin>>m; while(m--)solv(); }