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