[ABC257F] Teleporter Setting 题解

1.题目

洛谷传送门

2.思路

我们可以把不确定的点当成真实存在的 \(0\) 号点，建边的时候就正常连即可。

然后我们来看一个样例：

1 - 2 - 0
3 - 4 - 5

当我们把 \(0\) 号点看成 \(3\) 号点时，答案就是 \(1\) 号点到 \(0\) 号点的距离加上 \(3\) 号点到 \(5\) 号点的距离。

然后我们再看：

1 - 2
0 - 3 - 4 - 5

当我们把 \(0\) 号点看成 \(2\) 号点时，答案就是 \(1\) 号点到 \(2\) 号点的距离加上 \(0\) 号点到 \(5\) 号点的距离。

注意还有一种用不到 \(0\) 号点的情况：

1 - 2 - 5
0 - 3 - 4

那么答案就是 \(1\) 号点到 \(5\) 号点的距离。

综上所述，对于每个将 \(0\) 号点当成 \(i\) 号点的方案，其答案为以上三种情况结果的最小值。

3.代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 1000010;
typedef pair <int, int> PII;

int n, m;
int h[N], e[N], ne[N]; 
int dis1[N], dis2[N], st[N];
int idx;

void add (int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dijkstra1 () { //最短路，求出 1 号点到每个点的距离
	memset (dis1, 0x3f, sizeof dis1);
	dis1[1] = 0;
	
	priority_queue <PII, vector <PII>, greater <PII> > p;
	p.push ({0, 1});
	
	while (!p.empty ()) {
		auto t = p.top ();
		p.pop ();
		
		int ver = t.second, dit = t.first;
		
		if (st[ver]) {
			continue;
		}
		
		st[ver] = true;
		for (int i = h[ver]; i != -1; i = ne[i]) {
			int j = e[i];
			if (dis1[j] > dit + 1) {
				dis1[j] = dit + 1;
				p.push ({dis1[j], j});
			}
		}
	}
}

void dijkstra2 () { //最短路，求出 N 号点到每个点的距离
	memset (dis2, 0x3f, sizeof dis2);
	memset (st, 0, sizeof st); //注意要把判断数组清空
	dis2[n] = 0;
	
	priority_queue <PII, vector <PII>, greater <PII> > p;
	p.push ({0, n});
	
	while (!p.empty ()) {
		auto t = p.top ();
		p.pop ();
		
		int ver = t.second, dit = t.first;
		
		if (st[ver]) {
			continue;
		}
		
		st[ver] = true;
		for (int i = h[ver]; i != -1; i = ne[i]) {
			int j = e[i];
			if (dis2[j] > dit + 1) {
				dis2[j] = dit + 1;
				p.push ({dis2[j], j});
			}
		}
	}
}

int main () {
	cin >> n >> m;
	memset (h, -1, sizeof h);
	
	while (m --) {
		int a, b;
		cin >> a >> b;
		add (a, b); //建边，而且是双向边
		add (b, a);
	}
	
	dijkstra1 ();
	dijkstra2 ();

	int ans = 0;
	for (int i = 1; i <= n; i ++) {
		ans = min ({dis1[n], dis1[0] + dis2[i], dis1[i] + dis2[0]});
      //dis1[i] 存 i 号点到 1 号点的距离
      //dis2[i] 存 i 号点到 N 号点的距离
		if (ans == 0x3f3f3f3f) cout << -1 << ' ';//如果没有答案
		else cout << ans << ' ';
	}
	return 0;
}