kmjp's blog

競技プログラミング参加記です

dwangoプログラミングコンテスト予選 2016 : C - メンテナンス明け

二分探索解法は思い浮かばなかった。
http://dwango2016-prelims.contest.atcoder.jp/tasks/dwango2016qual_c

問題

N個の駅をM個の路線がつないでいる。
各路線はいくつかの駅を結んでおり、双方向に移動可能である。また駅間の移動時間が与えられる。

駅SからTに至る最短時間を求めたい。
ただし、移動中最大1回だけ寝過ごすことがある。
寝過ごすと、今移動中の路線に対し終点駅まで問答無用で移動してしまう。

適切な移動経路を選んだ時、最悪なタイミングで寝過ごした場合の時間をどこまで最小化できるか。

解法

一旦寝過ごしてしまえば、後は普通に最短経路で移動できる。
そこでまずは寝過ごしを無視して、Tまでの最短経路を求めよう。

次に、寝過ごしの可能性を残した状態で、各頂点の最悪ケースを最小化する。
まずすでにTに到達している場合は残り移動時間は0確定である。
ここから他の頂点からTへの最悪ケースの移動時間を最小化しよう。

これはダイクストラを変形し、以下のように求めればよい。

  • 最悪ケースの移動時間の最小値が確定した頂点vがある
  • vを通る各路線について、隣接駅uからvに向けて移動することを考える。
    • 寝過ごさない場合、u→vの移動時間と、vからTへの移動時間の和がTへの最短時間である。
    • 寝過ごす場合、u→vの向きに終点まで移動し、あとは終点から最短経路でTに至る手順で最短時間が得られる。
    • 「最悪のタイミングで寝過ごす」ということは、u→vに移動する手順を取った場合、上記2パターンのうち最短時間が長い方を取ることになる。
    • この長い方の最短時間が、現在uが持ってるTへの最短時間最小値を更新する場合、ダイクストラの要領でuの最短時間をPriority_queueで管理してまたuの隣接駅からTへの最短時間を更新していけば良い。
int N,M;
int st,ed;
ll D[2][50500];
int L[505050];
vector<int> S[505050];
vector<int> W[505050];
vector<ll> Sum[505050];
vector<pair<int,int>> P[252525];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	cin>>st>>ed;
	FOR(i,M) {
		cin>>L[i];
		S[i].resize(L[i]);
		Sum[i].resize(L[i]);
		W[i].resize(L[i]-1);
		FOR(x,L[i]) {
			cin>>S[i][x];
			P[S[i][x]].push_back({i,x});
		}
		FOR(x,L[i]-1) {
			cin>>W[i][x];
			Sum[i][x+1]=Sum[i][x]+W[i][x];
		}
	}
	memset(D,0x3f,sizeof(D));
	D[1][ed]=0;
	priority_queue<pair<ll,int>> Q;
	Q.push({0,ed});
	while(Q.size()) {
		auto aa=Q.top();
		Q.pop();
		ll co=-aa.first;
		int cur=aa.second;
		if(D[1][cur]!=co) continue;
		FORR(r,P[cur]) {
			int ro=r.first;
			int id=r.second;
			if(id) {
				int tar=S[ro][id-1];
				ll co2=co+W[ro][id-1];
				if(D[1][tar]>co2) D[1][tar]=co2, Q.push({-co2,tar});
			}
			if(id<L[ro]-1) {
				int tar=S[ro][id+1];
				ll co2=co+W[ro][id];
				if(D[1][tar]>co2) D[1][tar]=co2, Q.push({-co2,tar});
			}
		}
	}
	
	ll mi=1LL<<60;
	D[0][ed]=0;
	Q.push({0,ed});
	while(Q.size()) {
		auto aa=Q.top();
		Q.pop();
		ll co=-aa.first;
		int cur=aa.second;
		if(D[0][cur]!=co) continue;
		FORR(r,P[cur]) {
			int ro=r.first;
			int id=r.second;
			if(id) {
				int tar=S[ro][id-1];
				ll co2=max(W[ro][id-1]+co,Sum[ro][L[ro]-1]-Sum[ro][id-1]+D[1][S[ro].back()]);
				if(D[0][tar]>co2) D[0][tar]=co2, Q.push({-co2,tar});
			}
			if(id<L[ro]-1) {
				int tar=S[ro][id+1];
				ll co2=max(W[ro][id]+co,Sum[ro][id+1]+D[1][S[ro][0]]);
				if(D[0][tar]>co2) D[0][tar]=co2, Q.push({-co2,tar});
			}
		}
	}
	
	
	cout<<D[0][st]<<endl;
}

まとめ

状態遷移に手こずったけど、まあ解けて良かった。