代码随想录算法【Day60】

94.城市间货物运输 I
思绪
焦点思想是 队列优化的 Bellman-Ford 算法，利用队列存储待松弛的节点，并避免重复参加队列，提高效率。每次取出队首元素，对其毗邻节点进行松弛操作，若间隔更新，则将该节点参加队列，直到队列为空。终极输出最短路径，若无法到达终点，则输出 “unconnected”。
代码

1. #include <iostream>
2. #include <vector>
3. #include <queue>
4. #include <list>
5. #include <climits>
6. using namespace std;
8. struct Edge {
9.     int to;
10.     int val;
11.     Edge(int t, int w): to(t), val(w) {}
12. };
14. int main() {
15.     int n, m, p1, p2, val;
16.     cin >> n >> m;
18.     vector<list<Edge>> grid(n + 1);
19.     vector<bool> isInQueue(n + 1);
21.     for(int i = 0; i < m; i++){
22.         cin >> p1 >> p2 >> val;
23.         grid[p1].push_back(Edge(p2, val));
24.     }
26.     int start = 1;
27.     int end = n;
29.     vector<int> minDist(n + 1 , INT_MAX);
30.     minDist[start] = 0;
32.     queue<int> que;
33.     que.push(start);
35.     while (!que.empty()) {
36.         int node = que.front(); que.pop();
37.         isInQueue[node] = false;
38.         for (Edge edge : grid[node]) {
39.             int from = node;
40.             int to = edge.to;
41.             int value = edge.val;
42.             if (minDist[to] > minDist[from] + value) {
43.                 minDist[to] = minDist[from] + value;
44.                 if (!isInQueue[to]) {
45.                     que.push(to);
46.                     isInQueue[to] = true;
47.                 }
48.             }
49.         }
50.     }
52.     if (minDist[end] == INT_MAX) cout << "unconnected" << endl;
53.     else cout << minDist[end] << endl;
54. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。