結ぶ町の片方が決まっていないテレポーターを 可変テレポーター と呼ぶことにします。

解法 \(1\)

可変テレポーターのつなぐ先が町 \(T\) であるとします。最小の時間を達成する経路においては町 \(T\) を \(2\) 回以上訪ねる事はないため、経路における可変テレポーターの使用の仕方は次の \(4\) 通りしかありません。

• 可変テレポーターを使用しない。
• 別の町から町 \(T\) へ移動するのに可変テレポーターを使用し、それ以外には一度も使用しない。
• 町 \(T\) から別の町へ移動するのに可変テレポーターを使用し、それ以外には一度も使用しない。
• 別の町から町 \(T\) へ移動するのに可変テレポーターを使用し、その直後に 町 \(T\) から別の町へ移動するのに可変テレポーターを使用する。それ以外には一度も使用しない。

\(4\) 通りそれぞれについて、かかる時間の最小値を考えてみましょう。

ここで、可変テレポーターを使わなかったときの町 \(1\) から 町 \(x\) への移動にかかる最小の時間を \(d_1(x)\) 分、町 \(x\) から 町 \(N\) への移動にかかる最小の時間を \(d_N(x)\) 分とします。 ただし、到達できない場合は \(\infty\) 分かかるとします。 また、可変テレポーターのすでに決まっているもう片端となっている町の番号の重合を \(S\) とします。

1.可変テレポーターを使用しない場合

この時かかる最小の時間は明らかに\(d_1(N)\) 分です。これは \(T\) によりません。

2. 別の町から町 \(T\) へ移動するのに可変テレポーターを使用し、それ以外には一度も使用しない場合

町 \(1\) \(\to\cdots \to\) 町 \(x\) \((x\in S)\) \(\to\) 町 \(T\) \(\to\cdots \to\) 町 \(N\) という形で移動することになります。このときかかる最小の時間は \(d_1(x)+1+d_N(T)\) 分で表されます。 よって、この場合の最小値は \(\displaystyle\min_{x\in S} (d_1(x)+1+d_N(T))=d_N(T)+1+\displaystyle\min_{x\in S} d_1(x)\) で表されます。

3. 町 \(T\) から別の町へ移動するのに可変テレポーターを使用し、それ以外には一度も使用しない場合

ほぼ上のパターンと同様で、町 \(1\) \(\to\cdots \to\) 町 \(T\to\) 町 \(y\) \((y\in S)\) \(\to\cdots\to\) 町 \(N\) という形で移動することになります。このときかかる最小の時間は \(d_1(T)+1+d_N(y)\) 分で表されます。 よって、この場合の最小値は \(\displaystyle\min_{y\in S} (d_1(T)+1+d_N(y))=d_1(T)+1+\displaystyle\min_{y\in S} d_N(y)\) で表されます。

4.別の町から町 \(T\) へ移動するときおよびその直後に 町 \(T\) から別の町へ移動するのに可変テレポーターを使用し、それ以外には一度も使用しない場合

町 \(1\) \(\to\cdots \to\) 町 \(x\) \((x\in S)\) \(\to\) 町 \(T\to\) 町 \(y\) \((y\in S)\) \(\to\cdots\to\) 町 \(N\) という形で移動することになります。このときかかる最小の時間は \(d_1(x)+1+1+d_N(y)\) 分で表されます。 よって、この場合の最小値は \(\displaystyle\min_{x,y\in S} (d_1(x)+1+1+d_N(y))=2+\displaystyle\min_{x\in S} d_1(x)+\displaystyle\min_{y\in S} d_N(y)\) で表されます。

よって、各 \(T\) ごとにこの \(4\) つの値を求め、最小値が求められれば良いです。 式の形から、\(T\) によらず \(d_1(N), \displaystyle\min_{x\in S} d_1(x), \displaystyle\min_{y\in S} d_N(y)\)の値、および 各 \(T\) について \(d_1(T), d_N(T)\) の値が求まっていれば、それらを元に計算することができます。

ここで、\(d_1(x)\) および \(d_N(x)\) の値は町 \(1\) および町 \(N\) から始めた幅優先探索によって \(O(N+M)\) で求めることができます。 \(|S|\leq N\) であることに注意すると、\(\displaystyle\min_{x\in S} d_1(x), \displaystyle\min_{y\in S} d_N(y)\) についても、\(d_1(x)\), \(d_N(x)\) の計算結果からそれぞれ \(O(N)\) で求めることができます。

よって、この問題を \(O(N+M)\) で解くことができました。

解法 \(2\) (仮想頂点を用いる方法)

仮想的に町 \(N+1\) を付け加えて、可変テレポーターのもう片端をそちらに結ぶことを考えます。

このとき、各 \(i\) に対する答えは町 \(N+1\) と町 \(i\) を \(0\) 分で移動できる 特殊テレポーター を加えた時の町 \(1\) から町 \(N\) まで移動するのにかかる時間の最小値に一致します。

この時、最小時間を達成する経路としてあり得るものとして

• 特殊テレポーターを使わない経路
• 特殊テレポーターを町 \(i\to\) 町 \(N+1\) の向きに使う経路
• 特殊テレポーターを町 \(N+1\to \) 町 \(i\) の向きに使う経路

の \(3\) 種類があります。 ここで、仮想頂点と可変テレポーターを加えた (ただし、特殊テレポーターは加えない) 時の町 \(1\) から 町 \(x\) への移動にかかる最小の時間を \(d'_1(x)\) 分、町 \(x\) から 町 \(N\) への移動にかかる最小の時間を \(d'_N(x)\) 分とすると、それぞれの経路におけるかかる時間(分)の最小値はそれぞれ、

• \(d'_1(N)\)
• \(d'_1(i)+d'_N(N+1)\)
• \(d'_1(N+1)+d'_N(i)\)

となります。よって、この仮想頂点らを付け加えたグラフにおいて \(d'_1(x)\), \(d'_N(x)\) を幅優先探索によって求めればよいです。 計算量は解法 \(1\) と同様に \(O(N+M)\) となります。

c++ による実装例(解法 \(1\) ) :

#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for(int i = 0; i < n; ++i)
#define N 300010
#define INF (int)1e+9

int main(void) {
	int n, m;
	bool ex[N];
	bool used[N];
	rep(i, N)ex[i] = false;
	vector<int>e[N];
	int d[2][N];
	queue<int>q;
	int mn[2];
	int x, y;

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> x >> y;
		if (x == 0)ex[y - 1] = true;
		else {
			e[x - 1].push_back(y - 1);
			e[y - 1].push_back(x - 1);
		}
	}

	for (int i = 0; i < n; i++)d[0][i] = INF;
	for (int i = 0; i < n; i++)used[i] = false;
	mn[0] = INF;
	used[0] = true;
	d[0][0] = 0;
	q.push(0);
	while (!q.empty()) {
		x = q.front();
		q.pop();
		if (ex[x])mn[0] = min(mn[0], d[0][x]);
		y = e[x].size();
		for (int i = 0; i < y; i++) {
			if (!used[e[x][i]]) {
				used[e[x][i]] = true;
				d[0][e[x][i]] = d[0][x] + 1;
				q.push(e[x][i]);
			}
		}
	}

	for (int i = 0; i < n; i++)d[1][i] = INF;
	for (int i = 0; i < n; i++)used[i] = false;
	mn[1] = INF;
	used[n - 1] = true;
	d[1][n - 1] = 0;
	q.push(n - 1);
	while (!q.empty()) {
		x = q.front();
		q.pop();
		if (ex[x])mn[1] = min(mn[1], d[1][x]);
		y = e[x].size();
		for (int i = 0; i < y; i++) {
			if (!used[e[x][i]]) {
				used[e[x][i]] = true;
				d[1][e[x][i]] = d[1][x] + 1;
				q.push(e[x][i]);
			}
		}
	}

	for (int i = 0; i < n; i++) {
		x = min(d[0][n - 1], mn[0] + mn[1] + 2);
		x = min(x, mn[0] + 1 + d[1][i]);
		x = min(x, mn[1] + 1 + d[0][i]);
		if (x < INF)cout << x;
		else cout << -1;
		if (i < (n - 1))cout << " ";
		else cout << endl;
	}

	return 0;
}