Let’s call a Teleporter a variable Teleporter if one of the towns it connects is undetermined.

Solution \(1\)

Let’s say the variable Teleporters are connected to town \(T\). In the path that achieves the minimum path, you don’t need to visit Town \(T\) twice or more, so there are only four ways to use variable Teleporters in the path:

• Not using variable Teleporters at all.
• Using variable Teleporters only once to travel from another town to Town \(T\).
• Using variable Teleporters only once to travel from Town \(T\) to another town.
• Using variable Teleporters exactly twice: once to travel from another town to Town \(T\), and once to travel from Town \(T\) to another town.

For each of the four cases, let us consider the minimum time required.

Here, we denote by \(d_1(x)\) the minimum time (in minutes) required to travel from Town \(1\) to Town \(x\), and by \(d_N(x)\) the minimum time (in minutes) required to travel from Town \(x\) to Town \(N\). Here, if it is impossible to travel, we assume that it takes \(\infty\) time. Also, let \(S\) be the set of indices of Towns which are the other ends of the variable Teleporters, which are already determined.

1.If variable Teleporters are not used at all

Obviously, it takes \(d_1(N)\) minutes at minimum, independent of \(T\).

2. If variable Teleporters are used only once to travel from another town to Town \(T\)

The path will be as follows: Town \(1\) \(\to\cdots \to\) Town \(x\) \((x\in S)\) \(\to\) Town \(T\) \(\to\cdots \to\) Town \(N\). It takes \(d_1(x)+1+d_N(T)\) minutes at minimum. Thus, the minimum value in this case is represented by \(\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. If variable Teleporters are used only once to travel from Town \(T\) to another town

It is almost as same as the case right above, in which the path will be as follows: Town \(1\) \(\to\cdots \to\) Town \(T\to\) Town \(y\) \((y\in S)\) \(\to\cdots\to\) Town \(N\). It takes \(d_1(T)+1+d_N(y)\) minutes at minimum. Thus, the minimum value in this case is represented by \(\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. If variable Teleporters are used exactly twice: once to travel from another town to Town \(T\), and once to travel from Town \(T\) to another town

The path will be as follows: Town \(1\) \(\to\cdots \to\) Town \(x\) \((x\in S)\) \(\to\) Town \(T\to\) Town \(y\) \((y\in S)\) \(\to\cdots\to\) Town \(N\). It takes \(d_1(x)+1+1+d_N(y)\) minutes at minimum. Thus, the minimum value in this case is represented by \(\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)\).

Therefore, it is sufficient to find these four values for each \(T\) and find their minimum. By the form of the expression, we can see that all that we need is \(d_1(N), \displaystyle\min_{x\in S} d_1(x), \displaystyle\min_{y\in S} d_N(y)\) which are independent of \(T\) and \(d_1(T), d_N(T)\) for each \(T\); then we can calculate the minimum value based on them.

Here, note that the values of \(d_1(x)\) and \(d_N(x)\) can be found by Breadth-First Search (BFS) in a total of \(O(N+M)\) time. Since \(|S|\leq N\), we can also find \(\displaystyle\min_{x\in S} d_1(x)\) and \(\displaystyle\min_{y\in S} d_N(y)\) based on the results of \(d_1(x)\) and \(d_N(x)\) in a total of \(O(N)\) time.

Hence, the problem has been solved in a total of \(O(N+M)\) time.

Solution \(2\) (using a virtual vertex)

Consider an additional virtual vertex, Town \(N+1\), to which the another ends of the variable Teleporters are connected.

Then, the answer for each \(i\) coincides to the minimum time required to travel from Town \(1\) to Town \(N\) when we add a special Teleporter that enables us to travel between Town \(N+1\) and Town \(i\).

In this case, the path that achieves the minimum are either:

• a path that does not use the special Teleporter,
• a path that uses the special Teleporter only once to travel from Town \(i\) to Town \(N+1\), or
• a path that uses the special Teleporter only once to travel from Town \(N+1\) to Town \(i\).

Here, denoting by \(d'_1(x)\) the minimum time (in minutes) required to travel from Town \(1\) to Town \(x\) when the virtual vertex and the variable Teleporter (but not the special Teleporter) is added, and by \(d'_N(x)\) the minimum time (in minutes) required to travel from Town \(x\) to Town \(N\) in the same condition, then the minimum time (in minutes) required for each pattern of path is:

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

Therefore, it is sufficient to find \(d'_1(x)\) and \(d'_N(x)\) with BFS on this graph with the virtual vertex. The time complexity is \(O(N+M)\), which is the same as Solution \(1\).

Sample code in C++ (Solution \(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;
}