スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

AOJ 2200 Mr. Rito Post Office

わからなくてぐぐりました。
http://d.hatena.ne.jp/sune2/20120719/1342723320

z[i]からz[i+1]に移動するとき、

陸路のみ
陸路 → 海路 → 陸路

のうち、どちらかのタイプの経路を辿る。

この考え方で実装するとうまくいきます。
dp[i][j]に対して、i-1のとき船があった場所をkとし
z[i-1] →(陸路)→ k →(海路)→ j →(陸路)→ z[i]
と進む事で船を場所jに移し自分はz[i]に移動することができます。
k==jのとき、すなわち船を移動させる必要がないときは、
必ずしもkを経由する必要がないのでz[i-1]からz[i]の陸最短路で良い。
これがわからなくて何回かWAくらった。

#define N 200
#define M 10000
#define R 1000
#define INF 1000000

int main(){
while(1){
int n,m,r;
int sea[N][N];
int land[N][N];
int dp[R][N];
int z[R];

scanf("%d%d",&n,&m);
if(!n&&!m)break;

//陸路と海路を別々に全点対最短路を求める
for(int i=0;i for(int j=0;j if(i==j){
sea[i][j] = 0;
land[i][j] = 0;
}else{
sea[i][j] = INF;
land[i][j] = INF;
}
}
}
for(int i=0;i int x,y,t;
char s;
scanf("%d %d %d %c",&x,&y,&t,&s);
if(s=='S'){
sea[x-1][y-1] = t;
sea[y-1][x-1] = t;
}else{
land[x-1][y-1] = t;
land[y-1][x-1] = t;
}
}
for(int k=0;k for(int i=0;i for(int j=0;j sea[i][j] = min(sea[i][j],sea[i][k]+sea[k][j]);
land[i][j] = min(land[i][j],land[i][k]+land[k][j]);
}
}
}

scanf("%d",&r);
for(int i=0;i scanf("%d",&z[i]);
z[i]--;
}

//dp[i][j]をjに船をおいてz[i]まで進んだ時にかかる最短の時間
for(int i=0;i dp[0][i] = sea[z[0]][i] + land[i][z[0]];
for(int j=1;j dp[j][i] = INF;
}
}
for(int i=1;i for(int j=0;j for(int k=0;k dp[i][j] = min(
dp[i][j],
dp[i-1][k]+land[z[i-1]][k]+sea[k][j]+land[j][z[i]] );
if(k==j) dp[i][j] = min(dp[i][j],dp[i-1][j]+land[z[i-1]][z[i]]);
}
}
}

int ans = INF;
for(int i=0;i ans = min(ans,dp[r-1][i]);
}
cout << ans << endl;
}
return 0;
}


コメントの投稿

非公開コメント

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。