AOJ 2200 Mr. Rito Post Office

働き方改革！！！

問題

Mr. Rito Post Office | Aizu Online Judge

感想

全探索したい、そう思えたら勝ち。

船をどう使えばいいのかというのは全部見ていかないと行けなさそうですよね。

まあ、全探索をまともにできるわけがないので、DPになりますが。

dp[i][j] := 船がjにある状態でi番目まで配達が終わったときの最小値

です、遷移は陸地のみの移動の時と、船を使った時の移動をそれぞれやっていきましょう。

経路については陸と海を別けるといい感じになりますね。

船を使うときは、どこで降りるのか、ｎ通り見ます。

ということで計算量がO(rn^2)で間に合います(ゼロの数は丁寧に数えましょう)。

DPの練習としてはなかなかいい問題かも。

コード

#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG_MODE
	#define DBG(n) n;
#else
	#define DBG(n) ;
#endif
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int WWW = 0;WWW < (n);WWW++)cerr << v[WWW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000LL
#define MOD 1000000007

typedef long long ll;
typedef pair<ll,ll> P;

ll sd[222][222];
ll ld[222][222];
ll dp[1111][222];

int main(){
	int n,m;
	while(cin >> n >> m,n|m){
		
		REP(i,222){
			REP(j,222){
				sd[i][j] = LLINF;
				ld[i][j] = LLINF;
			}
			REP(j,1111)dp[j][i] = LLINF;
		}
		
		REP(i,222){
			sd[i][i] = 0;
			ld[i][i] = 0;
		}
		
		REP(i,m){
			ll a,b,c;char d;
			cin >> a >> b >> c >> d;
			a--;b--;
			if(d == 'S'){
				sd[a][b] = min(sd[a][b],c);
				sd[b][a] = min(sd[b][a],c);
			}
			else{
				ld[a][b] = min(ld[a][b],c);
				ld[b][a] = min(ld[b][a],c);
			}
		}
		
		ll r;cin >> r;
		vector<ll> v(r);REP(i,r)cin >> v[i],v[i]--;
		
		REP(k,222)REP(i,222)REP(j,222){
			sd[i][j] = min(sd[i][j],sd[i][k]+sd[k][j]);
			ld[i][j] = min(ld[i][j],ld[i][k]+ld[k][j]);
		}
		
		dp[0][v[0]] = 0;
		
		REP(i,r-1){
			REP(j,n){
				if(dp[i][j] != LLINF){
					dp[i+1][j] = min(dp[i+1][j],dp[i][j]+ld[v[i]][v[i+1]]);
					REP(k,n){
						dp[i+1][k] = min(dp[i+1][k],dp[i][j]+ld[v[i]][j]+sd[j][k]+ld[k][v[i+1]]);
					}
				}
			}
		}
				
		ll ans = LLINF;
		REP(i,n)ans = min(ans,dp[r-1][i]);
		
		cout << ans << endl;
	}
	return 0;
}