今天的两道题都看题解了，感觉用堆来优化dijkstra算法的方式还是有点不熟悉，即使是看懂了原理，自己上手写代码的时候也感觉也不出来，第二道关于Bellman_ford算法的题从原理上来说不难理解，完全看懂这个算法的流程以后感觉代码也没有很难写。
47. 参加科学大会（卡码网，堆优化版）
这道题用堆优化版做的改进之处在于每次在dijkstra三部曲的第一步，也就是寻找距离源点最近的节点时，直接从小顶堆的顶部取出即可，无需再通过一个for循环来寻找离源点最近的节点，小顶堆会自动维护堆中的节点顺序。因此我们只需要在第一步中取出对应的节点current，在第二步中直接将current节点对应的visited数组对应的位置赋值为true，而第三步则将与current节点相连的节点与源点的距离进行更新，被更新的节点将被加入小顶堆中，被加入小顶堆的节点需要满足：1.该节点从未被探索过；2.可以通过current节点到达（从源点出发也一定能到达）；3.且当前节点与起点之间的距离（从current节点到当前节点的距离+起点到current节点的距离） < current节点加入路线之前当前节点与起点之间的距离。其余地方和昨天朴素版是一样的。
#include<iostream>
#include<vector>
#include<list>
#include <climits>
#include<queue>
using namespace std;
typedef struct Edge{
int to; //链接的下一节点
int val; //权值
Edge(int t, int w): to(t), val(w) {} // 构造函数
}Edge;
class MyCompare{
public:
bool operator()(const pair<int, int>& a, const pair<int, int>& b){
return a.second > b.second; //权职大的排在底部
}
};
int main(){
int N, M;
cin >> N >> M; //N个车站（节点），M条路（边）
vector<list<Edge>> grid(N + 1); //用邻接表记录整个公交线路图
for(int i = 0; i < M; i++){
int S, E, V;
cin >> S >> E >> V; // S -> E 花费V单位的时间
grid[S].push_back(Edge(E, V));
}
int start = 1;
int end = N;
vector<bool> visited(N + 1, false); //记录访问过的站点
vector<int> minDist(N + 1, INT_MAX); //记录各个站点到起始站点的最短距离
minDist[start] = 0;
//定义优先队列，存储元素为pair<int, int>类型，pair<节点编号，源点到该节点的权值>
//底层实现指定为vector，
//自定义的比较仿函数指定为MyCompare
priority_queue<pair<int, int>, vector<pair<int, int>>, MyCompare> My_pq;
My_pq.push(pair<int, int> (start, 0));
while(!My_pq.empty()){
//第一步，选源点到哪个节点近且该节点未被访问过
pair<int, int> current = My_pq.top();
My_pq.pop();
//第二步，该最近节点被标记访问过
visited[current.first] = true;
//第三步，更新非访问节点到源点的距离（即更新minDist数组）
for(Edge e : grid[current.first]){
if(!visited[e.to] && e.val + minDist[current.first] < minDist[e.to]){
//当前遍历到的边的节点尚未被访问，且当前节点与起点之间的距离
//（从current节点到当前节点的距离+起点到current节点的距离）
// < current节点加入路线之前当前节点与起点之间的距离
minDist[e.to] = e.val + minDist[current.first];
My_pq.push(pair<int, int> (e.to, minDist[e.to]));
}
}
}
if(minDist[end] == INT_MAX) cout << -1 << endl;
else cout << minDist[end] << endl;
return 0;
}
94. 城市间货物运输 I（卡码网）
这道题感觉“松弛”的概念还比较新奇，我觉得一刷只要记住几个结论就行了，先不要去问为什么。
1.边的权值存在负数的情况不能用dijkstra算法，而Bellman_ford算法是比较适用的；
2.Bellman_ford算法的核心思想是 对所有边进行松弛n-1次操作（n为节点数量），从而求得目标最短路。
3.对所有边松弛n次，相当于计算 起点到达与起点n条边相连的节点的最短距离。
有上面的结论以后，我们需要明确，对于n个节点，要得到最终的结果，我们需要对**“能松弛到的边”**松弛n - 1次（即循环n - 1次），什么叫“能松弛到的边”？对于第一次循环，第二次循环，不一定能保证地图中所有的边都会执行松弛操作，因为一条边能被松弛的条件之一就是这条边的起点是可到达的（表现为被更新为其他值，而不是初始值INT_MAX）,所以在每一次循环中，只能对“能松弛到的边”进行松弛。另外，我觉得不仅仅是bellman_ford算法是一种动态规划，在之前的dijkstra算法也可以算动态规划吧，这些算法都在循环中不断维护最短路径值。另外再讲一个小细节，在循环中，循环变量能用引用一定要用引用，不要为了省事直接无脑用auto，我在遍历边进行松弛时，用auto就超时了，用vector &就可以直接通过，用引用不用额外创建临时变量，这样更加节省时间。
#include<iostream>
#include<vector>
#include <climits>
using namespace std;
int main(){
int n, m;
cin >> n >> m; //N个车站（节点），M条路（边）
vector<vector<int>> edges; //存储所有边
for(int i = 0; i < m; i++){
int S, E, V;
cin >> S >> E >> V; // S -> E 花费V单位的时间
edges.push_back({S, E, V});
}
vector<int> minDist(n + 1, INT_MAX);
int start = 1;
int end = n;
minDist[start] = 0;
for(int i = 1; i < n; i++){ //每循环一次，就对所有的边松弛一次
for(vector<int> &edge : edges){
int from = edge[0]; //边的起点
int to = edge[1]; //边的终点
int val = edge[2]; //权值
if(minDist[from] != INT_MAX && minDist[from] + val < minDist[to]){
//更新起点已经被探索的边
minDist[to] = minDist[from] + val;
}
}
}
if(minDist[end] == INT_MAX) cout << "unconnected" << endl;
else cout << minDist[end] << endl;
return 0;
}
还有两天，训练营就结束了，加油加油！！！