代码随想录第46天|

#include<bits/stdc++.h>
using namespace std;
//定义小顶堆
class mycomparison{public:bool operator()(const pair<int,int> &lhs,const pair<int,int> &rhs){return lhs.second>rhs.second;}
};
//定义一个姐沟通储存带权重的边
struct Edge{int to;int val;Edge(int t,int v):to(t),val(w){}
};
int main(){int n,m,p1,p2,val;cin>>n>>m;vector<list<Edge>>  grid(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);//记录顶点是否被访问过vector<bool> visited(n+1,false);//利用小顶堆/优先队列 存放<节点，源点到该节点的权值>priority_queue<pair<int,int>,vector<pair<int,int>>,mycomparison> pq;pq.push(pair<int,int>(start,0));minDIst[start]=0;visited[start]=true;while(!pq.empty()){pair<int,int> cur=pq.top();pq.pop();//小顶堆中储存着点到源点的最短距离if(visited[cur.first])continue;visited[cur.first]=true;for(Edge edge:grid[cur.first]){if(!visited[edge.to]&&minDist[cur.first]+edge.val<minDist[edge]){minDist[edge.to]=minDist[cur.first]+edge.val;pq.push(pair<int,int>(edge.to,minDist[edge.to]));}}}if(minDist[end]==INT_MAX) cout<<-1<endl;else cout<<minDist[end]<<endl;}

#include<bits/stdc++.h>
using namespace std;
int main(){int n,m.p1,p2,val;cin>>n>>>m;vector<vector<int>> grid;for(int i=0;i<m;i++){cin>>p1>>p2>>val;https://www.programmercarl.com/images/system/dark.svg   grid.push_back({p1,p2,val});}int start=1;inr end=n;vector<int> minDist(n+1,INT_MAX);minDist[start]=0;//n-1次松弛for(int i=1;i<n;i++){for(vector<int> &side:grid){int from=side[0];int to=side[1];int price=side[2];//松弛操作if(minDist[from]!=INT_MAX&&minDist[to]>minDIst[from]+price){minDist[to]=minDist[from]+price;}}}if (minDist[end] == INT_MAX) cout << "unconnected" << endl; // 不能到达终点else cout << minDist[end] << endl; // 到达终点最短路径
}

主要是两个算法：

迪杰斯特拉（堆优化版）：

使用优先队列储存边 （小顶堆不能修改元素）遍历最短边 eloge

使用vector<list<edge>> 的形式方便遍历边：

不能有负权值的原因可能会先便利到短边 再想用长边-负权值边不可以 贪心思想错误

bellford_man(解决负权值的问题）：

n-1次relax 每一次relax 会找到距离当前结点隔i隔结点的最短路径 所以一共需要n-1次

利用{from,to,val}记录

遍历每一条边的to同时观察from不为INT——MAX更新 minDist更新最短路径