kojingharangの日記

SRM 573 Div1 450 SkiResorts

22:56 |

• N 個の地点があってその高さが A[i] で与えられる。また、地点間に道があるかどうかが road[N][N] で与えられる。
• 道があって高さが同じか低い位置にしか移動できない。必要なら各地点の高さを変えて地点 0 から N-1 まで移動したい。
• 高さの変化の合計の最小値を求める問題。できなければ -1 を返す。
• 1≦N≦50

• パスが１個決まったとして、そのパス上の高さの中間値のとこに合わせればいいのか？？
• 後まで見ないと最初の方の高さが決まらないよなぁ
• 地点の他にその時の高さをどうにか管理する必要がありそう
• 高さは N 通りしかないので、「ある地点をどの高さにしたか」をグラフのノードとすると最短経路っぽくなりそう
• 書いたけど最後のやつが合わない

• （あとで）

• エッジのコストがなんか怪しかった。あと高さが同じか低い位置に向かうときだけエッジを張るようにした。
• 最後に地点 N-1 での各高さにおけるポテンシャルが一番低いやつが答え。
• priority_queue は小さいものから返してくれるようにしてほしいなぁ

• ↓あとで(accepted in practice room)

class SkiResorts {
	public:
	long long minCost(vector <string> R, vector <int> A) {
		int N=R.size();
		ll INF = 1LL<<60;
		VI po(N*N, INF);
		priority_queue<PII, vector<PII>, greater<PII> > q;
		REP(j, N) {
			po[j]=abs(A[j]-A[0]);
			q.push(MP(po[j], j));
		}
		int end=0;
		ll ans = INF;
		while(q.size()) {
			ll pot =  q.top().first;
			int cur = q.top().second;
			int cur_n = cur/N;
			int cur_h = cur%N;
			q.pop();
			if(pot > po[cur]) continue;
			end += cur_n==N-1;
			if(end==N) break;
			REP(i, N) {
				if(R[cur_n][i]=='Y') {
					REP(j, N) {
						if(A[cur_h] < A[j]) continue;
						int cost = abs(A[j]-A[i]);
						if(po[cur] + cost < po[i*N+j]) {
							po[i*N+j] = po[cur] + cost;
							q.push(MP(po[i*N+j], i*N+j));
						}
					}
				}
			}
		}
		
		REP(i, N) ans=min(ans, po[(N-1)*N+i]);
		return ans==INF ? -1 : ans;
	}
};

ツイートする