yukicoder : No.1308 ジャンプビーコン

久々のFirst Accept。
https://yukicoder.me/problems/no/1308

問題

木を成す無向グラフが与えられる。
各辺には距離が設定されている。

この木において、指定された頂点Q[i]を順にたどりたい。
その際、普通に辺を速度1で移動するほか、ビーコンを用いた移動もできる。

移動中、どこか1個の頂点を経由した際にビーコンを設置できる。
ビーコンは同時に1個しか設置できず、2個目を設置すると即座に1個目が無効になる。
ビーコンへの移動は、時間Cで可能である。

指定頂点を順にたどる最短時間を求めよ。

解法

dp(i,v) := 頂点vにビーコンを置いた状態で、Q[i]に到達する最短時刻
とする。dp(i,*)からdp(i+1,*)を考えよう。
D(u,v) := uとvの(ビーコンを使わない)最短移動時間とする。

• ビーコンの配置を変えない場合、dp(i+1,v) = dp(i,v) + dp(Q[i],Q[i+1])
• ビーコンを再配置する場合
  • まず各頂点vに至る最短時間T(v)を求める。これはT(v)=min(dp(i,u)+C+D(u,v)) (u==Q[i]の時はCがかからない)で求められる。愚直に行うとこれはO(N^2)かかるが、ダイクストラ法を使えばO(NlogN)で収まる。
  • その後、vにビーコンを設置してQ[i+1]に向かうことを考えるとdp(i+1,v)=T(v)+D(v,Q[i+1])

int N,Q,C;
int X[3030];
vector<pair<int,int>> E[3030];
ll D[3030][3030];

ll from[3030];
ll to[3030];
ll d[3030];

void dfs(int cur,int pre,int start,ll d) {
	D[start][cur]=d;
	FORR(e,E[cur]) if(e.first!=pre) dfs(e.first,cur,start,d+e.second);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q>>C;
	FOR(i,N-1) {
		cin>>x>>y>>r;
		E[x-1].push_back({y-1,r});
		E[y-1].push_back({x-1,r});
	}
	FOR(i,N) dfs(i,i,i,0);
	FOR(i,Q) {
		cin>>X[i];
		X[i]--;
	}
	FOR(i,N) from[i]=1LL<<60;
	from[X[0]]=0;
	FOR(i,Q-1) {
		int s=X[i],t=X[i+1];
		// 動かさない
		FOR(j,N) to[j]=from[j]+D[s][t];
		
		priority_queue<pair<ll,int>> PQ;
		FOR(j,N) {
			
			if(j==s) d[j]=from[j];
			else d[j]=from[j]+C;
			PQ.push({-d[j],j});
		}
		while(PQ.size()) {
			ll co=-PQ.top().first;
			int cur=PQ.top().second;
			PQ.pop();
			if(d[cur]!=co) continue;
			FORR(e,E[cur]) if(d[e.first]>co+e.second) {
				d[e.first]=co+e.second;
				PQ.push({-d[e.first],e.first});
			}
		}
		FOR(j,N) to[j]=min(to[j],d[j]+D[j][t]);
		swap(from,to);
	}
	ll ret=1LL<<60;
	FOR(i,N) ret=min(ret,from[i]);
	cout<<ret<<endl;
	
	
	
}

まとめ

あんまりデバッグしてないのに一発で通ってびっくり。