题目复现
题目描述
Spojland 政府在城市中规划了一些地点，准备建设道路。
输入格式
第一行是一个整数 \(N\)，表示政府计划修建的道路数量。
接下来有 \(N\) 行，每行包含三个整数 \(A\)、\(B\) 和 \(W\)。其中，\(A\) 和 \(B\) 是修路连接的两个地点，\(W\) 是从 \(A\) 到 \(B\) 或从 \(B\) 到 \(A\) 的固定旅行费用。
再接下来的一行包含一个整数 \(U\)，Rohit 希望从该地点出发，去往其他地方。
随后一行包含一个整数 \(Q\)，代表他想要执行的查询次数，用于查找旅行费用。
接下来的 \(Q\) 行，每行包含一个整数 \(V\)（目的地），需要计算从 \(U\) 前往 \(V\) 的最低花费。
输出格式
对于每个查询，输出一行结果。如果无法从地点 \(U\) 到达地点 \(V\)，则输出 'NO PATH'。
输入输出样例 #1
输入 #1
7
0 1 4
0 3 8
1 4 1
1 2 2
4 2 3
2 5 3
3 4 2
0
4
1
4
5
7
输出 #1
4
5
9
NO PATH
说明/提示
- \(1 \le N \le 10^5\)
- \(1 \le A, B \le 10^5\)
- \(1 \le W \le 10^9\)
- \(1 \le U \le 10^5\)
- \(1 \le Q \le 10^5\)
- \(1 \le V \le 10^5\)
题解
题目分析
很明显，这是一道单源最短路的题，可以使用 Dijkstra 来做这道题（如果是骗分的也可以试试 Floyd），而且还可以说这就是一道 Dijkstra 的版子。
接下来我将会简单说一下 Dijkstra。
Dijkstra
这个算法可以简单概括为“Dijkstra = BFS + 贪心”，大体步骤如下：
| 步骤 | 做法 | 具体操作 | 结果 |
|---|---|---|---|
| \(1\) | 从起点 \(s\) 出发，用 BFS 扩展它的邻居节点 | 把这些邻居点放到一个集合 \(A\) 中，并记录这些点到 \(s\) 的距离 | |
| \(2\) | 选择距离 \(s\) 最近的邻居 \(v\)，继续用 BFS 扩展 \(v\) 的邻居 | 首先在 \(A\) 中找到距离 \(s\) 最小的点 \(v\)，把 \(v\) 的邻居点放到 \(A\) 中；如果 \(v\) 的邻居经过 \(v\) 中转，到 \(s\) 的距离更短，则更新这些邻居到 \(s\) 的距离；最后从集合 \(A\) 中移走 \(v\)，后面不再处理 \(v\) | 得到了从 \(s\) 到 \(v\) 的最短路径；\(v\) 的邻居更新了到 \(s\) 的距离 |
| \(3\) | 重复步骤 \(2\)，直到所有点都扩展到并计算完毕 | 集合 \(A\) 为空。计算出所有点到 \(s\) 的最短距离 |
按照这个步骤，实现 Dijkstra 其实并不难，现在给出参考实现代码。
实现
暴力做法（\(O(n^2)\)）
struct edge {int v, w;
};vector<edge> e[MAXN];
int dis[MAXN], vis[MAXN];void dijkstra(int n, int s) {memset(dis, 0x3f, (n + 1) * sizeof(int));dis[s] = 0;for (int i = 1; i <= n; i++) {int u = 0, mind = 0x3f3f3f3f;for (int j = 1; j <= n; j++)if (!vis[j] && dis[j] < mind) u = j, mind = dis[j];vis[u] = true;for (auto ed : e[u]) {int v = ed.v, w = ed.w;if (dis[v] > dis[u] + w) dis[v] = dis[u] + w;}}
}
优先队列做法（\(O(m\log m)\)）
struct edge {int v, w;
};struct node {int dis, u;bool operator>(const node& a) const { return dis > a.dis; }
};vector<edge> e[MAXN];
int dis[MAXN], vis[MAXN];
priority_queue<node, vector<node>, greater<node>> q;void dijkstra(int n, int s) {memset(dis, 0x3f, (n + 1) * sizeof(int));memset(vis, 0, (n + 1) * sizeof(int));dis[s] = 0;q.push({0, s});while (!q.empty()) {int u = q.top().u;q.pop();if (vis[u]) continue;vis[u] = 1;for (auto ed : e[u]) {int v = ed.v, w = ed.w;if (dis[v] > dis[u] + w) {dis[v] = dis[u] + w;q.push({dis[v], v});}}}
}
Dijkstra 总体上就这些内容了，那么接下来就可以编码了。
参考代码
#include<bits/stdc++.h>
#define int long long
#define Rint register int
#define fast_running ios::sync_with_stdio(false),std::cin.tie(nullptr),std::cout.tie(nullptr)
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 5, M = 1e5 + 5;
const int INF = 0x3f3f3f3f;
int m, s, cnt;
int head[N], dist[N], flag[N];
priority_queue<PII, vector<PII>, greater<PII>> q; //优先队列优化
struct edge {int from, to, next, w;
} e[M << 1];
void addedge(int u, int v, int w) { //建图 e[++cnt].from = u;e[cnt].to = v;e[cnt].next = head[u];e[cnt].w = w;head[u] = cnt;
}
void init() { //初始化 for (int i = 0; i < N; i++) {head[i] = -1;flag[i] = 0;dist[i] = INF;}cnt = 0;return;
}
void dijshort(int start) { //优先队列优化的 Dijkstra dist[start] = 0;q.push({dist[start], start});while (!q.empty()) {PII tp = q.top();q.pop();int id_x = tp.second, dist_x = tp.first;if (flag[id_x]) continue;flag[id_x] = 1;for (int i = head[id_x]; i != -1; i = e[i].next) {int v = e[i].to;if (dist[v] > dist_x + e[i].w) {dist[v] = dist_x + e[i].w;q.push({dist[v], v});}}}
}
signed main() {fast_running;cin >> m;init();for (int i = 1; i <= m; i++) {int u, v, w;cin >> u >> v >> w;addedge(u, v, w);addedge(v, u, w);}cin >> s;dijshort(s);int T, in;cin >> T;while (T--) {cin >> in;if (dist[in] == INF) cout << "NO PATH\n";else cout << dist[in] << '\n';}return 0;
}