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