TopCoder SRM 573 Div1 Medium SkiResorts

問題

n個の場所が、向きのないゲレンデによってつながっている。
つながっている箇所はroad[i][j], road[j][i]がYになっている。

それぞれの場所には高さがあり、i番目の高さ≧j番目の高さのとき、
iからjに移動することができる。

今、0番目の場所からn-1番目の場所に移動したい。
移動できるように、それぞれの場所の高さを変更することができる。
高さの変更には、元々の高さをx、変更後の高さをyとすると|x-y|のコストがかかる。
何箇所でも高さを自由に変更できるとき、
かかるコストの最小値を求めよ。

制約条件

n≦50
高さは10^9以下

方針

変更後の高さは、他の場所の高さ以外にする必要はない。
なので、dp[pos][height]を、posの場所を高さheightにしているときの最短コストとして、
これを更新していけばよい。
これはグラフの最短路問題である。

ループがあるかなとか思ったので、SPFAを使ってみた。
ダイクストラだと、グラフを適当にやりすぎるとTLEする場合があったらしくよかった。

ソースコード

const ll inf = 1ll << 50;
int n;
vector<vi> e;
ll h[50];
ll dp[50][50];
bool in[50][50];

class SkiResorts {
	public:
	long long minCost(vector <string> road, vector <int> altitude) {
		
		n = road.size();
		e.clear();
		e.resize(n);
		rep(i, n) rep(j, n) if(road[i][j] == 'Y') e[i].pb(j);
		rep(i, n) h[i] = altitude[i];
		rep(i, n) rep(j, n) dp[i][j] = inf;
		rep(i, n) dp[0][i] = abs(h[0] - h[i]);
		
		queue<int> q;
		rep(i, n){
			q.push(i);
			in[0][i] = 1;
		}
		while(!q.empty()){
			int c = q.front() / 50, he = q.front() % 50;
			q.pop();
			in[c][he] = 0;
			
			rep(i, e[c].size()) rep(j, n) if(h[he] >= h[j]){
				int to = e[c][i];
				
				ll nxt = dp[c][he] + abs(h[j] - h[to]);
				if(nxt < dp[to][j]){
					dp[to][j] = nxt;
					if(!in[to][j]){
						q.push(to * 50 + j);
						in[to][j] = 1;
					}
				}
			}
		}
		ll ans = inf;
		rep(i, n) ans = min(ans, dp[n - 1][i]);
		return ans >= inf ? -1 : ans;
	}
};