Cork

banbooooのブログ

統計、機械学習、数学に関する記事を投稿します。

Educational Codeforces Round 38 D問題

競プロ界ではとても有名(?)なダイクストラ法。
典型問題からちょっとひねった問題で個人的には良問だと思った。
codeforces.com

問題文の要約 (訳に脚色入ってます。)

n個の町とm本の道があって道には通行料が存在。コンサートが全ての町で行われるが、チケット料も町ごとに異なる。町iにいる人が、コンサートを一番安く見る時、その料金(他の町へ行くなら通行料往復分込み)を表示せよ。

アルゴリズム

まずグラフ構造に直す。n頂点m辺、辺の重みは往復分の通行料w_{ij} \times 2とできる。
さて、チケット料の情報をどう扱うかが今回最大の工夫ポイント。
まず、一つの頂点 v_s について考える。通常のダイクストラでは最初優先度付きキューに
(0,始点)をpushするが、今回は(チケット料  a , v_s)をpushする。
ここで下図のような例を考えて、頂点v_s からの最短距離の意味を考える。

このように、頂点v_sから頂点v_tまでの最短距離が、v_tからv_sへコンサートを見に行った時の最小の料金となっている。後は同様に全ての頂点に対して行えば良いのだが、最小の料金 = 最短距離 に対応しているので最初に(チケット料,v)を全ての頂点分pushしてダイクストラ法をやれば distance配列 (通常は始点からの距離を格納する配列)に本問題の答えが格納されている。
計算量は、最初にpushする分だけ増えて  O ( V + |E| \log |V|) \approx 10^6
(間違ってたらごめんなさい)

ソースコード

#include <bits/stdc++.h>
#define REP(i,n) for (long i=0;i<(n);i++)
#define FOR(i,a,b) for (long i=(a);i<(b);i++)
#define RREP(i,n) for(long i=n;i>=0;i--)
#define RFOR(i,a,b) for(long i=(a);i>(b);i--)
#define dump1d_arr(array) REP(i,array.size()) cerr << #array << "[" << (i) << "] ==> " << (array[i]) << endl;
#define dump2d_arr(array) REP(i,array.size()) REP(j,array[i].size()) cerr << #array << "[" << (i) << "]" << "[" << (j) << "] ==> " << (array[i][j]) << endl;
#define dump(x)  cerr << #x << " => " << (x) << endl;
#define CLR(vec) { REP(i,vec.size()) vec[i] = 0; } 
#define llINF (long long) 9223372036854775807
#define loINF (long) 2147483647
#define shINF (short) 32767
#define SORT(c) sort((c).begin(),(c).end())
#define MIN(vec) *min_element(vec.begin(), vec.end());
#define MAX(vec) *max_element(vec.begin(), vec.end());
using namespace std;
typedef long long LL;
typedef vector<LL> VL;
typedef vector<VI> VVL;
typedef pair<LL,LL> pr;
struct ver {LL di,node,prev;};
struct Order {
	bool operator() (ver const& a,ver const& b) const {
		return a.di > b.di || ((a.di == b.di) && (a.node > b.node));
	}
};
typedef priority_queue<ver,vector<ver>,Order> pq;

// ダイクストラ法
class Dijekstra {
private:
	vector<vector<pr>> E;
	vector<LL> dist;
	size_t V;
public:
	Dijekstra() : V(0) { }
	Dijekstra(size_t v) :
		V(v),E(v,vector<pr>(0)),dist(v,llINF) {}

	size_t size() { return V;}

	void add_edge_directed(LL from,LL to,LL dis){
		E[from].push_back(pr(to,dis));
	}

	void add_edge_undirected(LL from,LL to,LL dis){
		E[from].push_back(pr(to,dis));
		E[to].push_back(pr(from,dis));
	}	

	void dijekstra(VI weight){
		pq que;
		REP(i,weight.size()) que.push(ver{weight[i],i,i});

		while(! que.empty()){
			ver next = que.top();
			que.pop();
			LL next_v = next.node;
			if (dist[next_v] < next.di) continue; //決定済み
			dist[next_v] = next.di;
			
			REP(i,E[next_v].size()){
				pr e = E[next_v][i];
				if (dist[e.first] > next.di+e.second) {
                                       que.push(ver{next.di+e.second,e.first,next_v});
                                 }
			}
		}
	}

	vector<LL> result(void){
		return dist;
	}

	long result_query(long goal){
		return dist[goal];
	}
};


int main(void){
	long n,m,v,u;
	LL w;
	cin >> n >> m;

	Dijekstra dj(n);

	REP(i,m){
		cin >> u >> v >> w;
		dj.add_edge_undirected(u-1,v-1,w*2); //添え字に注意
	}

	VI weight(n);
	REP(i,n) cin >> weight[i];

	dj.dijekstra(weight);
	VI ans = dj.result();
	REP(i,n) cout << ans[i] << " ";
	cout << "\n";

	return 0;
}

注意

数は結構大きくなるのでlong long型じゃないと通らなかった。