题目描述
样例
//vector<pii> dijkstra写法
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
typedef pair<int,int> pii;
vector<pii >v[N];
bool st[N];
int dist[N];
int n,m;
int dij(){
memset(dist,0x3f,sizeof dist);
priority_queue<pii,vector<pii >,greater<pii> >q;
q.push({0,1});
dist[1]=0;
while(q.size()){
auto t=q.top();
q.pop();
int d=t.first,id=t.second;
if(st[id]==1) continue;//考虑存在重边的情况
//因为只要存在重边 那么所有重边的距离和该点都会入队 但是根据优先队列的排序 只会选择距离最短的边
//而一旦弹出了这个点 这个点就是当前还没确定距离的最短点 所以这个点就要被挖掉 下次在由于重边的原因在
//由于重边的原因遍历到这个点时 就会之际continu;
st[id]=1;
for(auto i:v[id]){
if(dist[i.second]>d+i.first){
dist[i.second]=d+i.first;
q.push({d+i.first,i.second});
}
}
}
if(dist[n]==0x3f3f3f3f) return -1;
else return dist[n];
}
int main(){
cin>>n>>m;
while(m--){
int x,y,w;
cin>>x>>y>>w;
v[x].push_back({w,y});
}
cout<<dij()<<endl;
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla