IOI 2011-day2 Crocodile's Underground City

問題文 : ワニの地下都市(pdf注意)

解法 :
出口につけばすぐに出ることが出来るので, 出口のノードのコストは0にしておく.

そうでないすべてのノードについて, "出口までたどり着ける最短時間" "出口までたどり着ける2 番目の最短時間"を状態としてdijkstra を行う. ただし, 2 番目の最短時間の昇順で優先にノードを取っていく.

前計算にO(N log N), dijkstra にO(M log N) で, 計O((M + N) log N) 時間でこの問題が解ける.

コード :

#include <cstring>
#include <algorithm>
#include <climits>
#include <vector>
#include <queue>

#define MAX_N (100000)
#define MAX_M (1000000)
#define INF (1ll << 34)

using namespace std;

typedef long long lint;

struct edge {
	int to;
	lint fcost, ncost;
	edge(int to, lint fcost = INF, lint ncost = INF) : to(to), fcost(fcost) {}
	edge(){}
};

bool operator < (const edge &a, const edge &b)
{
	return (a.ncost < b.ncost);
}

bool operator > (const edge &a, const edge &b)
{
	return (b < a);
}

vector<edge> G[MAX_N];
edge g[MAX_N];
lint cost[MAX_N];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	for (int i = 0; i < M; i++){
		G[R[i][0]].push_back(edge(R[i][1], L[i]));
		G[R[i][1]].push_back(edge(R[i][0], L[i]));
	}
	
	for (int i = 0; i < N; i++) cost[i] = INF;
	
	for (int i = 0; i < K; i++){
		cost[P[i]] = 0;
	}
	
	
	priority_queue<edge, vector<edge>, greater<edge> > pq;
	
	for (int i = 0; i < N; i++){
		if (cost[i]){
			g[i].to = i;
			g[i].fcost = g[i].ncost = INF;
			for (int j = 0; j < G[i].size(); j++){
				lint newcost = G[i][j].fcost + cost[G[i][j].to];
				if (newcost > g[i].ncost) continue;
				else if (newcost > g[i].fcost){
					g[i].ncost = newcost;
				}
				else {
					g[i].ncost = g[i].fcost;
					g[i].fcost = newcost;
				}
			}
			pq.push(g[i]);
		}
	}
	
	for (; pq.size(); pq.pop()){
		edge x = pq.top();
		
		if (cost[x.to] <= x.ncost) continue;
		
		cost[x.to] = x.ncost;
		
		for (int i = 0; i < G[x.to].size(); i++){
			int npos = G[x.to][i].to;
			lint newcost = G[x.to][i].fcost + cost[x.to];
			if (newcost > g[npos].ncost) continue;
			else if (newcost > g[npos].fcost){
				g[npos].ncost = newcost;
			}
			else {
				g[npos].ncost = g[npos].fcost;
				g[npos].fcost = newcost;
			}
			pq.push(g[npos]);
		}
	}
	
	return (cost[0]);
}