AtCoder蟻本 初級編 2-5 グラフ ②Roadblocks (POJ No.3255) （ダイクストラ法）

SoundHound Inc. Programming Contest 2018 -Masters Tournament- D - Saving Snuuk(400)

D - Saving Snuuk

概要

n頂点m辺の連結無向グラフが与えられ、各辺には2種類のコスト（コストA, コストBと分類）が与えられる。
頂点sから頂点tに移動するコストを考える。このとき頂点iを選ぶ。すると頂点sから頂点iまではコストAがかかり、頂点iから頂点tまではコストBがかかるとする。なお、選ぶ頂点にはs, tも含まれる。

0, 1, ..., n-1の各整数について次の問いに答えよ。

• 整数iについて、頂点番号(1-indexed)がiより大きい頂点を選んでコストを切り替える場合、かかるコストの最小値を求めよ。出力はコストの最小値がaであるとき、10^15-aとして出力せよ。

制約

2 ≦ n, m ≦10^5

方針

各頂点iについて、コストAベースのsからiまでの最短距離d1(i)と、コストBベースのtからiまでの最短距離d2(i)をダイクストラ法で求める。
あとは大きい方の整数から最短距離を考えてゆけばよい。

つまり、下記の通り。
整数n-1については、n-1で切り替えるしかないので、n-1の最短距離をd(n-1)とすると、d(n-1) = d1(n-1) + d2(n-1)で確定する。
整数n-2については、n-1で切り替えるかn-2で切り替えるかが選択できるので、d(n-2) = min(d(n-1), d1(n-2) + d2(n-2))。
整数n-3については、n-1, n-2, n-3の切り替えが選択できる。d(n-3) = min(d(n-2), d1(n-3) + d2(n-3))。
...

解答

Submission #2816212 - SoundHound Inc. Programming Contest 2018 -Masters Tournament-

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
 
// dijkstra
struct edge {ll to, cost;};
typedef pair<ll, ll> P; // firstはsからの最短距離, secondは頂点の番号
const ll INF = 1e15;
 
void dijkstra(vector<edge> g[], vector<ll>& d, ll s){
	d[s] = 0;
 
	priority_queue<P,vector<P>,greater<P> > que;
	que.push(P(0,s));
 
	while(!que.empty()){
		P p = que.top();
		que.pop();
 
		ll v = p.second;
		if(d[v] < p.first) continue; //後から最短パスが見つかった場合、先にqueに入っているものはここではじかれる
 
		for(ll i = 0; i < g[v].size(); i++){
			edge e= g[v][i];
			if(d[e.to] > d[v] + e.cost){
				d[e.to] = d[v] + e.cost;
				que.push(P(d[e.to], e.to));
			}
		}
	}
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	ll n, m, s, t;
	cin >> n >> m >> s >> t;
	s--;
	t--;
 
	vector<edge> g1[n];
	vector<edge> g2[n];
 
	rep(i, m){
		ll u, v, a, b;
		cin >> u >> v >> a >> b;
		u--;
		v--;
 
		g1[u].push_back((edge){v, a});
		g1[v].push_back((edge){u, a});
		g2[u].push_back((edge){v, b});
		g2[v].push_back((edge){u, b});
	}
 
	vector<ll> d1(n, INF);
	vector<ll> d2(n, INF);
 
	dijkstra(g1, d1, s);
	dijkstra(g2, d2, t);
 
	// rep(i, n) cout << d1[i] << (i == n-1 ? "\n" : ",");
	// rep(i, n) cout << d2[i] << (i == n-1 ? "\n" : ",");
 
	ll ans[n];
	rep(i, n) ans[i] = d1[i] + d2[i];
	rrep(i, n-1) ans[i] = min(ans[i], ans[i+1]);
 
	// rep(i, n) cout << ans[i] << (i == n-1 ? "\n" : ",");
	rep(i, n) cout << (1000000000000000 - ans[i]) << endl;
}