「AOJ1041～1050」の編集履歴（バックアップ）一覧はこちら
「AOJ1041～1050」(2013/02/10 (日) 12:52:51) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
----
*1045 Split Up!
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1045
戦闘力が与えられるので戦闘力の合計が均等になるように２チームにわける問題。
普通に解くだけなら全探索にちょっと枝刈で簡単に解いたけど、高速化してみた。
saikiAとsaikiBと半分半分で計算すれば2^20の計算量が2*2＾10の計算量に落ちる。
#include<stdio.h>
#include<set>
int sum,herf,n,datas[21],t,ans,nHerf;
std::set<int> herfSum;
std::set<int>::iterator it;
void saikiB(int deep,int now){
if(deep<n){
saikiB(deep+1,now+datas[deep]);
saikiB(deep+1,now);
}else{
if(now<=herf){
it=herfSum.upper_bound(herf-now);
if((*it)!=0)it--;
now+=(*it);
t=sum-now*2;
}else{
t=now*2-sum;
}
ans=ans>t?t:ans;
}
}
void saikiA(int deep,int now){
if(deep<nHerf){
saikiA(deep+1,now+datas[deep]);
saikiA(deep+1,now);
}else{
herfSum.insert(now);
}
}
int main(){
while(scanf("%d",&n)){
if(n==0)break;
sum=0;
ans=2000000000;
herfSum.clear();
for(int i=0;i<n;i++){
scanf("%d",&datas[i]);
sum+=datas[i];
}
herf=sum/2;
nHerf=n/2;
saikiA(0,0);
saikiB(nHerf,0);
printf("%d\n",ans);
}
}
----
*1046 Ghost Buster!
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1046
升目で区切られたマップ上を一定のルールで移動する幽霊を最短時間で捕まえる問題。
あるマスで捕まえるとき、そのマスまで最短時間で移動しそのマスに幽霊が来るのを待てばいい。
この簡単なことに気づくのにやたらと時間のかかった問題。
考え方さえ分かれば後は場合分けが少しめんどくさいだけの実装ゲーム。
#include<stdio.h>
#include<string.h>
// 0 1 2 3 4 5 6 7 8
const int dxs[]={0,0,0,0,-1,0,1,0, 0};
const int dys[]={0,0,1,0, 0,0,0,0,-1};
const int max=100000000;
char map[21][21];
bool gMoveMemo[21][21];
int moveMemo[21][21];
int h,w;
bool areaOut(int x,int y){
if(x<0||x>=w||y<0||y>=h) return true;
return false;
}
void saiki(int x,int y,int deep){
if(areaOut(x,y)||map[y][x]=='#'||moveMemo[y][x]<=deep) return;
moveMemo[y][x]=deep;
saiki(x+1,y,deep+1);
saiki(x-1,y,deep+1);
saiki(x,y+1,deep+1);
saiki(x,y-1,deep+1);
}
void print(){
for(int y=0;y<h;y++){
for(int x=0;x<w;x++){
printf("%2d",moveMemo[y][x]==max?-1:moveMemo[y][x]);
}
printf("\n");
}
}
bool setData(){
scanf("%d %d",&h,&w);
if(h+w==0)return false;
int sx,sy,gx,gy;
memset(gMoveMemo,true,sizeof(gMoveMemo));
for(int y=0;y<h;y++){
scanf("%s",&map[y]);
for(int x=0;x<w;x++){
moveMemo[y][x]=max;
if(map[y][x]=='A'){
sx=x;
sy=y;
}else if(map[y][x]=='B'){
gx=x;
gy=y;
}
}
}
saiki(sx,sy,0);
//print();
char com[12];
scanf("%s",com);
int size=strlen(com),count=1,nx,ny,ans=max,ansX,ansY,turn=0;
while(count!=0&&ans>turn){
count=0;
for(int p=0;p<size;p++){
nx=dxs[com[p]-'0']+gx;
ny=dys[com[p]-'0']+gy;
turn++;
if(areaOut(nx,ny)==false){
gx=nx;
gy=ny;
}
if(moveMemo[gy][gx]<=turn){
gMoveMemo[gy][gx]=false;
count++;
if(ans>turn){
ans=turn;
ansX=gx;
ansY=gy;
}
}else if(gMoveMemo[gy][gx]==true){
count++;
gMoveMemo[gy][gx]=false;
}else if(moveMemo[gy][gx]!=max){
count++;
}
}
}
if(ans==max)printf("impossible\n");
else printf("%d %d %d\n",ans,ansY,ansX);
return true;
}
int main(){
while(setData()){
}
}
*1047 Crop Circle
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1047
平面上に円が無数に与えられるので円の一番外側の外周(中身で囲まれた部分も含む)の距離を計算する問題。
解法
数学の公式通りに円の交点を求め、円i上の交点を反時計回りにmemo[i]に入れていきます。
memo[i]の要素AiとAi+1が外部を構成するなら円弧AiAi+1の中点Biも外周に属します。
Biが外周に属するなら円弧AiAi+1の長さを足していけばこの問題は解けます。
小数点以下１２桁指定でないと丸め誤差で不正回を食らうようなのでその点だけ要注意です。
#include<stdio.h>
#include<math.h>
#include<set>
struct circle{
double x,y,r,x2,y2,r2;
int no;
bool bad;//同心円でサイズが小さいことが判明したのは使わない
void set(int ino){
no=ino;
x2=x*x;
y2=y*y;
r2=r*r;
bad=false;
}
};
void setPoint(circle& c1,circle& c2,std::set<double> memo[101]){
if(c1.bad||c2.bad)return;//使わない円が来た
if(c1.x==c2.x&&c1.y==c2.y){
//計算誤差が怖いので念のため下と処理を分けておく
if(c1.r<c2.r)c1.bad=true;
else c2.bad=true;
return;
}
double len=sqrt(pow(c1.x-c2.x,2)+pow(c1.y-c2.y,2));
if(len<=fabs(c1.r-c2.r)){
//円の内側に入っていた
if(c1.r>=c2.r)c2.bad=true;
else c1.bad=true;
return;
}
if(c1.r+c2.r>len&&len>fabs(c1.r-c2.r)){
//交点が二つあることが判明したので
double x,y1,y2,cosA,sinA,tempX,tempY,ansR;
x=(c1.r2-c2.r2+len*len)/(2.0*len);
y1=sqrt(c1.r2-x*x);
y2=-y1;
//回転する
cosA=(c2.x-c1.x)/len;
sinA=(c2.y-c1.y)/len;
tempX=(cosA*x-sinA*y1);
tempY=sinA*x+cosA*y1;
//printf("<x=%lf,y=%lf>",tempX+c1.x,tempY+c1.y);
tempX=tempX/c1.r;
if(tempX>=1.0){
ansR=0;
}else if(tempX<=-1.0){
ansR=M_PI;
}else{
ansR=tempY<0?2*M_PI-acos(tempX):acos(tempX);
}
memo[c1.no].insert(ansR);
//二つ目の点を求める
tempX=(cosA*x-sinA*y2);
tempY=sinA*x+cosA*y2;
//printf("<x=%lf,y=%lf>\n",tempX+c1.x,tempY+c1.y);
tempX=tempX/c1.r;
//printf("(%lf)\n",tempX);
if(tempX>=1.0){
ansR=0;
}else if(tempX<=-1.0){
ansR=M_PI;
}else{
ansR=tempY<0?2*M_PI-acos(tempX):acos(tempX);
}
memo[c1.no].insert(ansR);
}
}
void setData(int n){
circle c,cs[101],c2;
for(int i=0;i<n;i++){
scanf("%lf %lf %lf",&c.x,&c.y,&c.r);
c.set(i);
cs[i]=c;
}
std::set<double> memo[101];//交点のメモ、各円に対して時計回りで記憶する
for(int i=0;i<n;i++){
memo[i].insert(0);//この円は交点を持つので
memo[i].insert(2*M_PI);//番兵
for(int j=0;j<n;j++){
if(i==j)continue;
setPoint(cs[i],cs[j],memo);
}
}
double ans=0;
std::set<double>::iterator it,nIt;
for(int i=0;i<n;i++){
if(cs[i].bad==true)continue;//別の円の内側に入っていた
//円を反時計回りに切り分けてその範囲が他の円に入るかを調べる
it=memo[i].begin();
nIt=it;
nIt++;
c=cs[i];
double r1,r2,r3,x1,y1,len1;
for(;nIt!=memo[i].end();it++,nIt++){
r1=(*it);
r2=(*nIt);
r3=(r1+r2)/2.0;
x1=c.r*cos(r3)+c.x;//切り分けた真中の点を求める
y1=c.r*sin(r3)+c.y;
bool bad=false;
for(int j=0;j<n;j++){
if(i==j)continue;
if(cs[j].bad==true)continue;
c2=cs[j];
len1=(x1-c2.x)*(x1-c2.x)+(y1-c2.y)*(y1-c2.y);
if(len1<c2.r2){
bad=true;
break;
}
}
if(bad==false){
ans+=c.r*(r2-r1);
}
}
}
printf("%.12lf\n",ans);
}
int main(){
int n;
while(1){
scanf("%d",&n);
if(n==0)break;
setData(n);
}
}
*1048 Provident Housewife
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1048
グラフで表されたマップ上にスーパーがある。
スーパーを回って一番安く買い物をしかつ移動距離を一番短い買い物をしたときの金額と移動距離を求める問題。
解法
まずどの店も到達できることが保証されています。
次に一番安い金額に納めるという条件が最優先なので全ての店を回って一番安い店だけで買い物した場合から最低購入金額が決まります。
後は最低購入金額で売ってる店以外で物を買わないことに決めて店を回り、（一番安い金額で変えた品物のセットと今いるスーパーの組）を点に見立ててダイクストラ法で解きます。
#include<stdio.h>
#include<map>
#include<set>
#include<string>
#include<iostream>
#include<vector>
#include<queue>
struct Way{
int len,no;
};
struct Bay{
int shopNo,perm,len;
bool operator<(const Bay& b)const{
return len>b.len;
}
};
void calc(int n){
std::map<std::string,int> goodsMin;
std::map<std::string,int> goodsToBit;
std::map<std::string,int> shops[110];
int shopBits[110]={0};
int k,v;
std::string name;
for(int i=1;i<=n;i++){
std::cin>>k;
for(int j=0;j<k;j++){
std::cin>>name>>v;
if(goodsMin.find(name)==goodsMin.end()||goodsMin[name]>v){
goodsMin[name]=v;
}
shops[i][name]=v;
}
}
int q,bit=1,allSet=0;
scanf("%d",&q);
for(int i=0;i<q;i++){
std::cin>>name;
goodsToBit[name]=bit;
allSet+=bit;
bit*=2;
}
for(int i=1;i<=n;i++){
for(std::map<std::string,int>::iterator it=shops[i].begin();it!=shops[i].end();it++){
name=(*it).first;
v =(*it).second;
if(goodsToBit.find(name)!=goodsToBit.end()){
if(goodsMin[name]==v){
shopBits[i]|=goodsToBit[name];//namne商品が一番安い店なのでここ以外で買わない
}
}
}
}
int ans=0;
for(std::map<std::string,int>::iterator it=goodsToBit.begin();it!=goodsToBit.end();it++){
if(goodsMin.find((*it).first)==goodsMin.end()){
ans=-1;
break;
}else{
ans+=goodsMin[(*it).first];
}
}
//for(int i=0;i<=n;i++){
// printf("%d ",shopBits[i]);
//}
std::vector<Way> G[110];
Way way;
int m,s,t;
scanf("%d",&m);
for(int i=0;i<m;i++){
scanf("%d %d %d",&s,&t,&way.len);
way.no=t;
G[s].push_back(way);
way.no=s;
G[t].push_back(way);
}
if(ans==-1){
printf("impossible\n");
return ;
}
std::map<int,int> memo[110];
std::priority_queue<Bay> qu;
Bay bay,nextBay;
bay.shopNo=bay.len=bay.perm=0;
qu.push(bay);
while(qu.empty()==false){
bay=qu.top();
qu.pop();
if(bay.shopNo==0&&bay.perm==allSet)break;
if(memo[bay.shopNo].find(bay.perm)!=memo[bay.shopNo].end()&&memo[bay.shopNo][bay.perm]<=bay.len)continue;
memo[bay.shopNo][bay.perm]=bay.len;
for(int i=0;i<G[bay.shopNo].size();i++){
way=G[bay.shopNo][i];
nextBay.perm=(bay.perm|shopBits[way.no]);
nextBay.len =(bay.len+way.len);
nextBay.shopNo=way.no;
if(memo[nextBay.shopNo].find(nextBay.perm)!=memo[nextBay.shopNo].end()&&
memo[nextBay.shopNo][nextBay.perm]<=nextBay.len)continue;
qu.push(nextBay);
}
}
printf("%d %d\n",ans,bay.len);
}
int main(){
int n;
while(1){
std::cin>>n;
if(n==0)break;
calc(n);
}
}
*1049 Building Houses
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1049
仲の悪い住人の家を上手に間をあけて配置した時の最小距離を求める問題。
深さ優先による全探索と枝刈を組み合わせただけのシンプルコードで通るようです。
一応コード実行速度３位を取ったコードだが一位との差は大きい。
一位がどんな魔法を使ったのか気になるところ。
メモ化による枝刈をもっと高度化したというところかな？
#include<stdio.h>
#include<string.h>
#include<algorithm>
int ans,lens[11],data[11][11];
bool spents[11];
int n;
void saiki(int deep,int l){
if(deep==n){
if(ans==-1)ans=l;
ans=std::min(ans,l);
}else{
int back[11];
bool out=false;
memcpy(back,lens,sizeof(lens));
for(int i=0;i<n;i++){
if(spents[i]==false){
spents[i]=true;
int len=lens[i];
for(int j=0;j<n;j++){
if(spents[j]==false)lens[j]=std::max(len+data[i][j],lens[j]);
if(ans>-1&&ans<=lens[j]&&spents[j]==false)out=true;
}
if(out==false)saiki(deep+1,len);
out=false;
memcpy(lens,back,sizeof(back));
spents[i]=false;
}
}
}
}
void setData(){
ans=-1;
memset(data,0,sizeof(data));
for(int i=0;i<n;i++){
spents[i]=false;
lens[i]=0;
for(int j=0;j<n;j++){
scanf("%d",&data[i][j]);
data[i][j]=data[j][i]=std::max(data[i][j],data[j][i]);
}
}
saiki(0,0);
printf("%d\n",ans);
}
int main(){
while(1){
scanf("%d",&n);
if(n==0)break;
setData();
}
}
----
*1045 Split Up!
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1045
戦闘力が与えられるので戦闘力の合計が均等になるように２チームにわける問題。
普通に解くだけなら全探索にちょっと枝刈で簡単に解いたけど、高速化してみた。
saikiAとsaikiBと半分半分で計算すれば2^20の計算量が2*2＾10の計算量に落ちる。
#include<stdio.h>
#include<set>
int sum,herf,n,datas[21],t,ans,nHerf;
std::set<int> herfSum;
std::set<int>::iterator it;
void saikiB(int deep,int now){
if(deep<n){
saikiB(deep+1,now+datas[deep]);
saikiB(deep+1,now);
}else{
if(now<=herf){
it=herfSum.upper_bound(herf-now);
if((*it)!=0)it--;
now+=(*it);
t=sum-now*2;
}else{
t=now*2-sum;
}
ans=ans>t?t:ans;
}
}
void saikiA(int deep,int now){
if(deep<nHerf){
saikiA(deep+1,now+datas[deep]);
saikiA(deep+1,now);
}else{
herfSum.insert(now);
}
}
int main(){
while(scanf("%d",&n)){
if(n==0)break;
sum=0;
ans=2000000000;
herfSum.clear();
for(int i=0;i<n;i++){
scanf("%d",&datas[i]);
sum+=datas[i];
}
herf=sum/2;
nHerf=n/2;
saikiA(0,0);
saikiB(nHerf,0);
printf("%d\n",ans);
}
}
----
*1046 Ghost Buster!
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1046
升目で区切られたマップ上を一定のルールで移動する幽霊を最短時間で捕まえる問題。
あるマスで捕まえるとき、そのマスまで最短時間で移動しそのマスに幽霊が来るのを待てばいい。
この簡単なことに気づくのにやたらと時間のかかった問題。
考え方さえ分かれば後は場合分けが少しめんどくさいだけの実装ゲーム。
#include<stdio.h>
#include<string.h>
// 0 1 2 3 4 5 6 7 8
const int dxs[]={0,0,0,0,-1,0,1,0, 0};
const int dys[]={0,0,1,0, 0,0,0,0,-1};
const int max=100000000;
char map[21][21];
bool gMoveMemo[21][21];
int moveMemo[21][21];
int h,w;
bool areaOut(int x,int y){
if(x<0||x>=w||y<0||y>=h) return true;
return false;
}
void saiki(int x,int y,int deep){
if(areaOut(x,y)||map[y][x]=='#'||moveMemo[y][x]<=deep) return;
moveMemo[y][x]=deep;
saiki(x+1,y,deep+1);
saiki(x-1,y,deep+1);
saiki(x,y+1,deep+1);
saiki(x,y-1,deep+1);
}
void print(){
for(int y=0;y<h;y++){
for(int x=0;x<w;x++){
printf("%2d",moveMemo[y][x]==max?-1:moveMemo[y][x]);
}
printf("\n");
}
}
bool setData(){
scanf("%d %d",&h,&w);
if(h+w==0)return false;
int sx,sy,gx,gy;
memset(gMoveMemo,true,sizeof(gMoveMemo));
for(int y=0;y<h;y++){
scanf("%s",&map[y]);
for(int x=0;x<w;x++){
moveMemo[y][x]=max;
if(map[y][x]=='A'){
sx=x;
sy=y;
}else if(map[y][x]=='B'){
gx=x;
gy=y;
}
}
}
saiki(sx,sy,0);
//print();
char com[12];
scanf("%s",com);
int size=strlen(com),count=1,nx,ny,ans=max,ansX,ansY,turn=0;
while(count!=0&&ans>turn){
count=0;
for(int p=0;p<size;p++){
nx=dxs[com[p]-'0']+gx;
ny=dys[com[p]-'0']+gy;
turn++;
if(areaOut(nx,ny)==false){
gx=nx;
gy=ny;
}
if(moveMemo[gy][gx]<=turn){
gMoveMemo[gy][gx]=false;
count++;
if(ans>turn){
ans=turn;
ansX=gx;
ansY=gy;
}
}else if(gMoveMemo[gy][gx]==true){
count++;
gMoveMemo[gy][gx]=false;
}else if(moveMemo[gy][gx]!=max){
count++;
}
}
}
if(ans==max)printf("impossible\n");
else printf("%d %d %d\n",ans,ansY,ansX);
return true;
}
int main(){
while(setData()){
}
}
*1047 Crop Circle
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1047
平面上に円が無数に与えられるので円の一番外側の外周(中身で囲まれた部分も含む)の距離を計算する問題。
解法
数学の公式通りに円の交点を求め、円i上の交点を反時計回りにmemo[i]に入れていきます。
memo[i]の要素AiとAi+1が外部を構成するなら円弧AiAi+1の中点Biも外周に属します。
Biが外周に属するなら円弧AiAi+1の長さを足していけばこの問題は解けます。
小数点以下１２桁指定でないと丸め誤差で不正回を食らうようなのでその点だけ要注意です。
#include<stdio.h>
#include<math.h>
#include<set>
struct circle{
double x,y,r,x2,y2,r2;
int no;
bool bad;//同心円でサイズが小さいことが判明したのは使わない
void set(int ino){
no=ino;
x2=x*x;
y2=y*y;
r2=r*r;
bad=false;
}
};
void setPoint(circle& c1,circle& c2,std::set<double> memo[101]){
if(c1.bad||c2.bad)return;//使わない円が来た
if(c1.x==c2.x&&c1.y==c2.y){
//計算誤差が怖いので念のため下と処理を分けておく
if(c1.r<c2.r)c1.bad=true;
else c2.bad=true;
return;
}
double len=sqrt(pow(c1.x-c2.x,2)+pow(c1.y-c2.y,2));
if(len<=fabs(c1.r-c2.r)){
//円の内側に入っていた
if(c1.r>=c2.r)c2.bad=true;
else c1.bad=true;
return;
}
if(c1.r+c2.r>len&&len>fabs(c1.r-c2.r)){
//交点が二つあることが判明したので
double x,y1,y2,cosA,sinA,tempX,tempY,ansR;
x=(c1.r2-c2.r2+len*len)/(2.0*len);
y1=sqrt(c1.r2-x*x);
y2=-y1;
//回転する
cosA=(c2.x-c1.x)/len;
sinA=(c2.y-c1.y)/len;
tempX=(cosA*x-sinA*y1);
tempY=sinA*x+cosA*y1;
//printf("<x=%lf,y=%lf>",tempX+c1.x,tempY+c1.y);
tempX=tempX/c1.r;
if(tempX>=1.0){
ansR=0;
}else if(tempX<=-1.0){
ansR=M_PI;
}else{
ansR=tempY<0?2*M_PI-acos(tempX):acos(tempX);
}
memo[c1.no].insert(ansR);
//二つ目の点を求める
tempX=(cosA*x-sinA*y2);
tempY=sinA*x+cosA*y2;
//printf("<x=%lf,y=%lf>\n",tempX+c1.x,tempY+c1.y);
tempX=tempX/c1.r;
//printf("(%lf)\n",tempX);
if(tempX>=1.0){
ansR=0;
}else if(tempX<=-1.0){
ansR=M_PI;
}else{
ansR=tempY<0?2*M_PI-acos(tempX):acos(tempX);
}
memo[c1.no].insert(ansR);
}
}
void setData(int n){
circle c,cs[101],c2;
for(int i=0;i<n;i++){
scanf("%lf %lf %lf",&c.x,&c.y,&c.r);
c.set(i);
cs[i]=c;
}
std::set<double> memo[101];//交点のメモ、各円に対して時計回りで記憶する
for(int i=0;i<n;i++){
memo[i].insert(0);//この円は交点を持つので
memo[i].insert(2*M_PI);//番兵
for(int j=0;j<n;j++){
if(i==j)continue;
setPoint(cs[i],cs[j],memo);
}
}
double ans=0;
std::set<double>::iterator it,nIt;
for(int i=0;i<n;i++){
if(cs[i].bad==true)continue;//別の円の内側に入っていた
//円を反時計回りに切り分けてその範囲が他の円に入るかを調べる
it=memo[i].begin();
nIt=it;
nIt++;
c=cs[i];
double r1,r2,r3,x1,y1,len1;
for(;nIt!=memo[i].end();it++,nIt++){
r1=(*it);
r2=(*nIt);
r3=(r1+r2)/2.0;
x1=c.r*cos(r3)+c.x;//切り分けた真中の点を求める
y1=c.r*sin(r3)+c.y;
bool bad=false;
for(int j=0;j<n;j++){
if(i==j)continue;
if(cs[j].bad==true)continue;
c2=cs[j];
len1=(x1-c2.x)*(x1-c2.x)+(y1-c2.y)*(y1-c2.y);
if(len1<c2.r2){
bad=true;
break;
}
}
if(bad==false){
ans+=c.r*(r2-r1);
}
}
}
printf("%.12lf\n",ans);
}
int main(){
int n;
while(1){
scanf("%d",&n);
if(n==0)break;
setData(n);
}
}
*1048 Provident Housewife
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1048
グラフで表されたマップ上にスーパーがある。
スーパーを回って一番安く買い物をしかつ移動距離を一番短い買い物をしたときの金額と移動距離を求める問題。
解法
まずどの店も到達できることが保証されています。
次に一番安い金額に納めるという条件が最優先なので全ての店を回って一番安い店だけで買い物した場合から最低購入金額が決まります。
後はその品物を一番安く売ってる店以外で物を買わないことに決めて店を回り、（一番安い金額で変えた品物のセットと今いるスーパーの組）を点に見立ててダイクストラ法で解きます。
#include<stdio.h>
#include<map>
#include<set>
#include<string>
#include<iostream>
#include<vector>
#include<queue>
struct Way{
int len,no;
};
struct Bay{
int shopNo,perm,len;
bool operator<(const Bay& b)const{
return len>b.len;
}
};
void calc(int n){
std::map<std::string,int> goodsMin;
std::map<std::string,int> goodsToBit;
std::map<std::string,int> shops[110];
int shopBits[110]={0};
int k,v;
std::string name;
for(int i=1;i<=n;i++){
std::cin>>k;
for(int j=0;j<k;j++){
std::cin>>name>>v;
if(goodsMin.find(name)==goodsMin.end()||goodsMin[name]>v){
goodsMin[name]=v;
}
shops[i][name]=v;
}
}
int q,bit=1,allSet=0;
scanf("%d",&q);
for(int i=0;i<q;i++){
std::cin>>name;
goodsToBit[name]=bit;
allSet+=bit;
bit*=2;
}
for(int i=1;i<=n;i++){
for(std::map<std::string,int>::iterator it=shops[i].begin();it!=shops[i].end();it++){
name=(*it).first;
v =(*it).second;
if(goodsToBit.find(name)!=goodsToBit.end()){
if(goodsMin[name]==v){
shopBits[i]|=goodsToBit[name];//namne商品が一番安い店なのでここ以外で買わない
}
}
}
}
int ans=0;
for(std::map<std::string,int>::iterator it=goodsToBit.begin();it!=goodsToBit.end();it++){
if(goodsMin.find((*it).first)==goodsMin.end()){
ans=-1;
break;
}else{
ans+=goodsMin[(*it).first];
}
}
//for(int i=0;i<=n;i++){
// printf("%d ",shopBits[i]);
//}
std::vector<Way> G[110];
Way way;
int m,s,t;
scanf("%d",&m);
for(int i=0;i<m;i++){
scanf("%d %d %d",&s,&t,&way.len);
way.no=t;
G[s].push_back(way);
way.no=s;
G[t].push_back(way);
}
if(ans==-1){
printf("impossible\n");
return ;
}
std::map<int,int> memo[110];
std::priority_queue<Bay> qu;
Bay bay,nextBay;
bay.shopNo=bay.len=bay.perm=0;
qu.push(bay);
while(qu.empty()==false){
bay=qu.top();
qu.pop();
if(bay.shopNo==0&&bay.perm==allSet)break;
if(memo[bay.shopNo].find(bay.perm)!=memo[bay.shopNo].end()&&memo[bay.shopNo][bay.perm]<=bay.len)continue;
memo[bay.shopNo][bay.perm]=bay.len;
for(int i=0;i<G[bay.shopNo].size();i++){
way=G[bay.shopNo][i];
nextBay.perm=(bay.perm|shopBits[way.no]);
nextBay.len =(bay.len+way.len);
nextBay.shopNo=way.no;
if(memo[nextBay.shopNo].find(nextBay.perm)!=memo[nextBay.shopNo].end()&&
memo[nextBay.shopNo][nextBay.perm]<=nextBay.len)continue;
qu.push(nextBay);
}
}
printf("%d %d\n",ans,bay.len);
}
int main(){
int n;
while(1){
std::cin>>n;
if(n==0)break;
calc(n);
}
}
*1049 Building Houses
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1049
仲の悪い住人の家を上手に間をあけて配置した時の最小距離を求める問題。
深さ優先による全探索と枝刈を組み合わせただけのシンプルコードで通るようです。
一応コード実行速度３位を取ったコードだが一位との差は大きい。
一位がどんな魔法を使ったのか気になるところ。
メモ化による枝刈をもっと高度化したというところかな？
#include<stdio.h>
#include<string.h>
#include<algorithm>
int ans,lens[11],data[11][11];
bool spents[11];
int n;
void saiki(int deep,int l){
if(deep==n){
if(ans==-1)ans=l;
ans=std::min(ans,l);
}else{
int back[11];
bool out=false;
memcpy(back,lens,sizeof(lens));
for(int i=0;i<n;i++){
if(spents[i]==false){
spents[i]=true;
int len=lens[i];
for(int j=0;j<n;j++){
if(spents[j]==false)lens[j]=std::max(len+data[i][j],lens[j]);
if(ans>-1&&ans<=lens[j]&&spents[j]==false)out=true;
}
if(out==false)saiki(deep+1,len);
out=false;
memcpy(lens,back,sizeof(back));
spents[i]=false;
}
}
}
}
void setData(){
ans=-1;
memset(data,0,sizeof(data));
for(int i=0;i<n;i++){
spents[i]=false;
lens[i]=0;
for(int j=0;j<n;j++){
scanf("%d",&data[i][j]);
data[i][j]=data[j][i]=std::max(data[i][j],data[j][i]);
}
}
saiki(0,0);
printf("%d\n",ans);
}
int main(){
while(1){
scanf("%d",&n);
if(n==0)break;
setData();
}
}
