WUPC2012 E : 会場への道

問題概要

重み付き無向グラフで2点間の最短路を求める。ただし最短路は4か7の倍数でなければならない。

解法

(ノード、今の時刻%28)を組にしてDijkstraする。

acceptされたコード

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

const int MAX_N = 1000;
const int INF = 1<<30;

typedef pair<int,int> edge;

int N, M;
vector< edge > graph[MAX_N];
int dist[MAX_N][28];

struct state{
	int dist;
	int n, d;
	state(){}
	state(int dist, int n, int d):dist(dist), n(n), d(d){}
};

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

void init(){
	scanf("%d%d", &N, &M);
	for(int i=0; i<M; ++i){
		int f, t, c;
		scanf("%d%d%d", &f, &t, &c);
		graph[f].push_back(edge(t,c));
		graph[t].push_back(edge(f,c));
	}
}

int solve(){
	priority_queue<state, vector<state>, greater<state> > que;
	que.push( state(0, 0, 0) );
	for(int i=0; i<N; ++i){
		fill(dist[i], dist[i]+28, INF);
	}
	dist[0][0] = 0;

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

		if(n != N-1)for(int i=0; i<(int)graph[n].size(); ++i){
			const int tar = graph[n][i].first;
			const int nd = dst + graph[n][i].second;
			if(nd < dist[tar][nd%28]){
				dist[tar][nd%28] = nd;
				que.push(state(nd, tar, nd%28));
			}
		}
	}

	int ans = INF;
	for(int i=0; i<28; ++i)if(i%4 == 0 || i%7 == 0){
		ans = min(ans, dist[N-1][i]);
	}
	return ans == INF ? -1 : ans;
}

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

	return 0;
}