一、解题思路
此题与 (Dijkstra)求最短路(I) 有什么本质上的区别？
-
两者(m)(边的数量)的数据范围基本一致，(I)是(10^5),(II)是(1.5*10^5)，是一个数量级的
-
(n)(结点数量)有明显区别：(I)是(500)上限，(II)是(1.5 * 10^5)。如果按(I)的方式去解，创建邻接矩阵，那个二维邻接矩阵就是 (1.5 * 10^5 * 1.5 * 10^5), 这样就太大了，内存爆掉，这就是使用邻接表更合适了。另外，可以采用小顶堆对朴素版本的(Dijkstra)进行一次优化。
二、C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> PII; // 维护距离和编号，所有是一个pair
int n, m; // 点的数量
int h[N], w[N], e[N], ne[N], idx; // 邻接表，稀疏图
int dist[N]; // 存储所有点到1号点的距离
bool st[N]; // 存储每个点的最短距离是否已确定
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra() {
//距1号点距离初始化
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
//STL的优先队列(小根堆)
priority_queue<PII, vector<PII>, greater<PII>> heap;//这是固定写法，背一下吧
heap.push({0, 1}); // first存储距离，second存储节点编号,1号点放进去
//bfs
while (heap.size()) {
//每次用堆的特性，找到堆里最小的点，就是距离最小的点
auto t = heap.top();
heap.pop();//找到就弹出
int k = t.second; //编号
int distance = t.first; // 距离
//如果已经处理过了,是一个冗余的备份(比如重边)
if (!st[k]) {
//标识已使用
st[k] = true;
//遍历每一条边
for (int i = h[k]; i != -1; i = ne[i]) {
int j = e[i];
if (dist[j] > distance + w[i]) {
dist[j] = distance + w[i]; //松弛
heap.push({dist[j], j}); //把j点放到优先队列中去
}
}
}
}
//如果松弛无效，表示无法到达
if (dist[n] == INF) return -1;
//返回最短距离
return dist[n];
}
int main() {
//读入优化
ios::sync_with_stdio(false);
cin >> n >> m;
//表头初始化,链式前向星专用
memset(h, -1, sizeof h);
//读入m条边
while (m--) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);//就算有重边，我们这里也不做处理，因为算法会保证如何最优
}
int t = dijkstra();
printf("%d
", t);
return 0;
}
三、问题集
-
优先队列的数据类型应该是怎样的呢？
我们知道优先队列应该用于快速寻找距离最近的点。由于优先队列只是将最小的那个元素排在前面，因此我们应该定义一种数据类型，使得它包含该节点的编号以及该节点当前与起点的距离。 -
如果一个结点到起点的最短距离可以随多个中间点的加入面变化，那不是加入队列多次吗，如何处理队列中的那个已经存入的元素？
事实上，不需要理会队列中的元素，而是再存入一个就行了。因为如果要发生变化，只能将节点与起点之间的距离变得更小，而优先队列恰好是先让最小的那个弹出。
因此，轮到某一个队列元素弹出的时候，如果有多个元素的节点编号相同，那么被弹出的一定是节点编号最小的一个。等到后面再遇到这个节点编号的时候，我们只需要将它忽略掉就行了。 -
(849)与(850)的代码互通吗？
因为(850)使用的是邻接表，而(849)使用的是邻接矩阵，所以，(850)的代码兼容性更强，支持更多的结点数，可以(AC)掉(849)，但反过来就不行了，(849)的代码会因为开不了(1.5*10^5*1.5*10^5)而导致开不出来二维矩阵，无法运行。