题目链接:https://ac.nowcoder.com/acm/contest/52431/J
思路:以1号节点走单源最短路,答案为两个询问点单源最短路之和,若使用另一种方法即SPFA理论得不到全部的分数!!
代码实现:
#include <bits/stdc++.h> using namespace std; using ll = long long; const int N = 100007, M = 100007 << 1; int n, m; vector<pair<int, int>> g[N];//邻接表存取无向有权图 bool vis[N]; //记录类似bfs节点是否走过 ll dis[N]; struct node { int v; ll w; friend bool operator<(const node &a, const node &b) { //重载小于号比较的是两个节点的权值 return a.w > b.w; } }; priority_queue<node> pq;//优先队列(小根堆)存取 void dijkstra(int st) { for (int i = 1;i <= n;i++) dis[i] = 1e18; //目前求最短路,故首先将每一个节点的距离赋值为一个极大值 dis[st] = 0; //初始设为0,距离从0开始加,起始节点为st pq.push({ st,0 }); //类似bfs基本思路,首先给优先队列中放入第一个元素 while (!pq.empty()) { int u = pq.top().v; //bfs基本操作 pq.pop(); if (vis[u]) continue;//如果遍历过该点,跳出此循环 vis[u] = 1; for (auto [v, w] : g[u]) {//利用C++17的auto快速遍历邻接表(遍历节点u的所有邻居) if (dis[v] > dis[u] + w) { dis[v] = dis[u] + w; //获取节点u到某一个节点最近的最短路长度 pq.push({ v,dis[v] }); //继续遍历节点v同u一样,获取v的最短路 } }//直至遍历到终点即已经没有邻居,所有的点都遍历到了, } } int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);//加快程序的执行速度 cin >> n >> m; for (int i = 1;i <= m;i++) { int u, v, w; cin >> u >> v >> w; g[u].push_back({ v,w }); g[v].push_back({ u,w });//无向图基本赋值方法,均赋值u->v,v->u } dijkstra(1);//从1号节点进行单源最短路遍历 int T; cin >> T; while (T--) { int s, t; cin >> s >> t; cout << dis[s] + dis[t] << '\n'; //由题意必须经过节点1,所以和为总的最短路 } return 0; }