day59|dijkstra（堆优化版）精讲,Bellman_ford 算法精讲

dijkstra（堆优化版）精讲

47. 参加科学大会（第六期模拟笔试） (kamacoder.com)

#include <iostream>
#include <vector>
#include <climits>
#include <queue>
#include <list>using namespace std;class myCmp{
public:bool operator()(const pair<int, int> &pair1, const pair<int, int> &pair2){return pair1.second > pair2.second;}
};
struct Edge{int to;  // 指向int val; // 权重Edge(int x, int y):to(x), val(y){ };
};int main(){int n, m, s, e, v;cin >> n >> m;vector<list<Edge>> grid(n + 1);priority_queue<pair<int, int>, vector<pair<int, int>>, myCmp> pq;  // 小顶堆，用于记录节点到起点的最近距离中的最近距离vector<int> visited(n + 1, 0);vector<int> minDist(n + 1, INT_MAX);  // 记录节点到起点的最近距离for(int i = 1; i <= m; i++){cin >> s >> e >> v;Edge edge(e, v);grid[s].push_back(edge); // 用邻接表记录路径}pq.push({1, 0});minDist[1] = 0;while(!pq.empty()){pair<int, int> curPair = pq.top();int cur = curPair.first;pq.pop();if(visited[cur] == 1){  // 第一次出现的一定是最小的continue ;}visited[cur] = 1;for(Edge edge : grid[cur]){if(visited[edge.to] == 0 && edge.val + minDist[cur] < minDist[edge.to]){minDist[edge.to] = edge.val + minDist[cur];pq.push({edge.to, minDist[edge.to]});}}}if(minDist[n] != INT_MAX){cout << minDist[n];}else{cout << "-1";}return 0;
}

Bellman_ford 算法精讲

94. 城市间货物运输 I (kamacoder.com)

#include <vector>
#include <iostream>
#include <algorithm>
#include <climits>using namespace std;int main(){int n, m, s, t, v;cin >> n >> m;vector<vector<int>> grids;vector<int> minDist(n + 1, INT_MAX);for(int i = 1; i<= m; i++){cin >> s >> t >> v;grids.push_back({s, t, v});}minDist[1] = 0;for(int i = 1; i <= n; i++){for(vector<int> &grid : grids){  // 对每条边进行对比int start = grid[0], end = grid[1], cost = grid[2];if(minDist[start] != INT_MAX && minDist[start] + cost < minDist[end]){  minDist[end] = minDist[start] + cost;}}}if(minDist[n] == INT_MAX){cout << "unconnected" << endl;}else{cout << minDist[n] << endl;}return 0;
}