SRM519 Div2 Medium - ThreeTeleports
問題
最初(sx,sy)にいる
1マス移動するのには1秒かかる
また3つのテレポート装置のペア(∴ 計6点)があり、それらを使うと片方の点から対応するもう片方の点に10秒で飛べる
(gx,gy)まで最短で何秒で行けるか
0 <= (全ての座標の数字) <= 10^9
解法
始点・終点・テレポート装置6点の計8頂点でグラフを作って最短距離を求める
実装
stringで与えられるテレポート装置の座標を数字にし、頂点0を始点、1〜6をテレポート装置、7を終点とする
→ 全ての異なる2点間にマンハッタン距離をコストとする辺を引く
→ テレポート装置のペア間(∴ 頂点1と2、3と4、5と6)にコスト10の辺を引く
→ DFSで最短距離を求める
class ThreeTeleports { public: ll d[10]; vector<int> x, y; vector<pair<int,ll> > e[10]; void rd(string &s) { int id = 0, n = s.size(); rep(i,4) { int sum = 0; while (id<n && s[id]!=' ') sum *= 10, sum += s[id++]-'0'; (i%2==0 ? x : y).push_back(sum); id++; } } void rec(int v) { each(i,e[v]) { int to = i.first, dis = i.second; if (d[to]>d[v]+dis) d[to] = d[v]+dis, rec(to); } } int shortestDistance(int sx, int sy, int gx, int gy, vector<string> s) { x.push_back(sx), y.push_back(sy); each(i,s) rd(i); x.push_back(gx), y.push_back(gy); rep(i,8) reps(j,i+1,8) { int c = abs(x[i]-x[j]) + abs(y[i]-y[j]); e[i].push_back({j,c}), e[j].push_back({i,c}); } rep(I,3) { int i = I*2+1; e[i].push_back({i+1,10}), e[i+1].push_back({i,10}); } reps(i,1,8) d[i] = 1ll<<60; rec(0); return d[7]; } };