TopCoder SRM 615 Div1 Medium LongLongTripDiv1

問題

N個の都市があり、n本の双方向に通行可能な道路で結ばれている。
i番目の道路はA[i]とB[i]を結んでいて、長さがD[i]である。


0番の都市からN-1番の都市へ、長さがちょうどTになるように道を通っていくことが出来るかを判別せよ。

制約条件

n, N≦50
D[i]≦10000
T≦10^18

方針

dist[i][j]を、0番の都市からi番目の都市へ、距離のmodをM(後述)にして行くときの最短距離とする。


Mの値にかかわらず次のことが言える。、dist[i][j]をダイクストラ法で埋めて、
dist[N-1][T % M]がTより大きかったらならN-1へちょうど距離Tでは行けない。
dist[N-1][T % M]がT以下だったら、パス上に長さMの倍数の閉路をくっつけることができれば、かつそのときに限りN-1へちょうど距離Tで行ける。


0番の都市に直接道がある都市xをひとつ適当にとって、
M = 2 * (0からxへの道の長さ)としたらどうか。


パスの最初にMの倍数の好きな閉路をくっつけられるので、
dist[N-1][T % M]がT以下だったら、N-1へちょうど距離Tでいける。

ソースコード

ll d[50][20000];

const string OK = "Possible";
const string NG = "Impossible";

class LongLongTripDiv1 {
	public:
	string isAble(int N, vector <int> A, vector <int> B, vector <int> D, long long T) {
		
		int n = A.size();
		int M = inf;
		vector<vector<pi> > e(N);
		priority_queue<pair<ll, pi> > q;
		
		rep(i, n){
			e[A[i]].pb(mp(B[i], D[i]));
			e[B[i]].pb(mp(A[i], D[i]));
		}
		if(e[0].size()) M = 2 * e[0][0].second;
		if(M == inf) return NG;
		
		rep(i, N) rep(j, M) d[i][j] = T + 1;
		q.push(mp(0, mp(0, 0)));
		
		while(!q.empty()){
			ll dist = -q.top().first;
			int c = q.top().second.first, m = q.top().second.second;
			q.pop();
			
			if(d[c][m] <= dist) continue;
			d[c][m] = dist;
			
			rep(i, e[c].size()){
				ll nd = dist + e[c][i].second;
				int nm = (m + e[c][i].second) % M;
				
				if(d[e[c][i].first][nm] > nd) q.push(mp(-nd, mp(e[c][i].first, nm)));
			}
		}
		
		return d[N - 1][T % M] <= T ? OK : NG;
	}
};