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