代码随想录算法【Day60】

94.城市间货物运输 I

思路

核心思想是 队列优化的 Bellman-Ford 算法，使用队列存储待松弛的节点，并避免重复加入队列，提高效率。每次取出队首元素，对其邻接节点进行松弛操作，若距离更新，则将该节点加入队列，直到队列为空。最终输出最短路径，若无法到达终点，则输出 “unconnected”。

代码

#include <iostream> #include <vector> #include <queue> #include <list> #include <climits> using namespace std; struct Edge { int to; int val; Edge(int t, int w): to(t), val(w) {} }; int main() { int n, m, p1, p2, val; cin >> n >> m; vector<list<Edge>> grid(n + 1); vector<bool> isInQueue(n + 1); for(int i = 0; i < m; i++){ cin >> p1 >> p2 >> val; grid[p1].push_back(Edge(p2, val)); } int start = 1; int end = n; vector<int> minDist(n + 1 , INT_MAX); minDist[start] = 0; queue<int> que; que.push(start); while (!que.empty()) { int node = que.front(); que.pop(); isInQueue[node] = false; for (Edge edge : grid[node]) { int from = node; int to = edge.to; int value = edge.val; if (minDist[to] > minDist[from] + value) { minDist[to] = minDist[from] + value; if (!isInQueue[to]) { que.push(to); isInQueue[to] = true; } } } } if (minDist[end] == INT_MAX) cout << "unconnected" << endl; else cout << minDist[end] << endl; }