Xmas Contest 2011 B : shortest path

問題概要

ノード数V(<10^5)の完全な無向グラフが与えられる。M(<10^5)個の辺については重みが指定されていて、それ以外の辺については重みは|v-u|*Dで与えられる。ある点からある点への最短路を求める問題。

解法

辺の数が多いので愚直にやるとTLEする。しかし、普通の辺を使うときは実は両隣に行くことだけを考えればよいことが分かる。それに気づけば辺数(M+N)程度で抑えられるのでDijkstraが間に合う。

acceptされたコード

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int MAX_N = 1e5;
const int INF = (int)1e9 + 10;

int N, M, D, S, T;
vector< pair<int,int> > graph[MAX_N];
int dist[MAX_N];

void init(){
	scanf("%d%d%d%d%d", &N, &M, &D, &S, &T);
	for(int i=0; i<M; i++){
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		graph[a].push_back(make_pair(b, c));
		graph[b].push_back(make_pair(a, c));
	}
}

struct state{
	int v, dist;
};

bool operator<(const state& lhs, const state& rhs){
	return lhs.dist > rhs.dist;
}

int solve(){
	fill(dist, dist + N, INF);

	dist[S] = 0;
	priority_queue<state> que;
	que.push((state){S, 0});

	while(!que.empty()){
		state tp = que.top(); que.pop();
		int v = tp.v, d = tp.dist;
		if(dist[v] < d){
			continue;
		}

		for(int i=0; i<(int)graph[v].size(); i++){
			int u = graph[v][i].first, nd = d + graph[v][i].second;
			if(nd < dist[u]){
				dist[u] = nd;
				que.push((state){u, nd});
			}
		}

		for(int k=0; k<2; k++){
			int u = v + (1-2*k), nd = d + D;
			if(0<=u && u<N && nd < dist[u]){
				dist[u] = nd;
				que.push((state){u, nd});
			}
		}
	}

	return dist[T];
}

int main(){
	init();
	printf("%d\n", solve());

	return 0;
}