ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 2200 Mr. Rito Post Office

問題文はこちら↓
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2200


・概要
グラフが与えられて、その最短経路を求める問題です。
各点を移動するときにいろいろ制約がありますが、問題文を読んだほうが分かりやすいと思うのであとは省略。


・解法
ワーシャルフロイド + DP で解くことができます。

まずワーシャルフロイドで陸移動・船移動のそれぞれにたいして、各点間の距離を求めておきます。
そのあとにDP[何個荷物を集めたか][船の現在地]をすれば解をだすことができます。


※余談
この問題、自分の中ではとても難しいなぁーと思いました。
最初にDPという発想が生まれなかったし、漸化式を立てるのもとても難しかったです。(というか若干チラ見してしまいました)
まだまだ精進が足りないなぁー・・・と。


ソースコード

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

#define REP(i,x,n) for(int i = x ; i < (int)(n) ; i++)
#define rep(i,n) REP(i,0,n)
static const int INF = 1000000;

int n,m,r;
int sea[201][201],land[201][201],order[1000];
int dp[1000][201];

void display(){
   for(int i = 0 ; i < r ; i++){
      for(int j = 1 ; j <= n ; j++){
	 cout << dp[i][j] << " ";
      }
      cout << endl;
   }
   cout << endl;
}

void warshall_floyd(){
   for(int k = 1 ; k <= n ; k++){
      for(int i = 1 ; i <= n ; i++){
	 for(int j = 1 ; j <= n ; j++){
	    if(i==j)sea[i][j] = land[i][j] = 0;
	    else{
	       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]);
	    }
	 }
      }
   }
}

int solve(){
   warshall_floyd();

   rep(i,r)rep(j,n+1)dp[i][j] = INF;
   dp[0][order[0]] = 0;
    
   for(int i = 0 ; i < r-1 ; i++){
      for(int j = 1 ; j <= n ; j++){
	 if(dp[i][j]==INF)continue;
	 dp[i+1][j] = min(dp[i+1][j], dp[i][j]+land[order[i]][order[i+1]]);
	 for(int k = 1 ; k <= n ; k++){
	    dp[i+1][k] = min(dp[i+1][k], dp[i][j]+land[order[i]][j]+sea[j][k]+land[k][order[i+1]]);
	 }
      }
   }
	    
   //display();

   int ans = INF;
   for(int j = 1 ; j <= n ; j++)ans = min(ans, dp[r-1][j]);
   return ans;
}

int main(){
   while(cin >> n >> m){
      if(n==0 && m==0)break;

      rep(i,n+1)rep(j,n+1)land[i][j] = sea[i][j] = INF;

      rep(i,m){
	 int x,y,t;
	 char sl;
	 cin >> x >> y >> t >> sl;
	 if(sl=='L'){
	    land[x][y] = min(land[x][y], t);
	    land[y][x] = min(land[y][x], t);
	 }
	 if(sl=='S'){
	    sea[x][y] = min(sea[x][y], t);
	    sea[y][x] = min(sea[y][x], t);
	 }
      }

      cin >> r;
      rep(i,r)cin >> order[i];

      cout << solve() << endl;
   }
   return 0;
}