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; }