迪杰特斯拉演算法堆優化
#include<bits/stdc++.h>
using namespace std;
/*Dijkstra演算法：
*1.初始化dis[start]=0,其他點,dis[]=無窮大;所有點初始化le[]=0
*2.在le[]=0的里面找dis最小的點x,令le[x]=1;
*3.更新x的鄰接點y,(x,y)邊的權值為W,若dis[y]>dis[x]+z,則dis[y]=dis[x]+z;
*4.重復2,3直到所有點都變為1;
*/
class N{
public:
int x;//可訪問的點
int w;//權值
bool operator < (N a) const{
return this->w>a.w;
}
N(int a,int b): x(a),w(b) {
}
N(){
x=0;
w=0;
}
}
};
const long inf=2147483647;
vector<N> vec[100005];//鄰接表
int dis[100005];
int n;
int m;
int s;
void dijkstra(int x){
int le[n+1];//確定點是否被訪問
priority_queue<N> que;
for(int i=1;i<=n;i++){
dis[i]=inf;
}
memset(le,0,sizeof(le));
que.push(N(x,0));
dis[x]=0;
while(que.empty()==0){
N t=que.top();
que.pop();
if(le[t.x]==1){
continue;
}
le[t.x]=1;
int len=vec[t.x].size();
for(int i=0;i<len;i++){
if(dis[vec[t.x][i].x]>dis[t.x]+vec[t.x][i].w){
dis[vec[t.x][i].x]=dis[t.x]+vec[t.x][i].w;
que.push(N(vec[t.x][i].x,dis[vec[t.x][i].x]));
}
}
}
}
int main()
{
int u,v,w;
cin>>n>>m>>s;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
vec[u].push_back(N(v,w));
//無向圖的話加上這個
//vec[v].push_back(N(u,w));
}
dijkstra(s);
for(int i=1;i<=n;i++)
{
cout<<dis[i]<<" ";
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/233939.html
標籤：其他