P4779 【模板】单源最短路径

本文主要是介绍P4779 【模板】单源最短路径，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目地址

---

注意点：

• 源点需要设置初始距离（0）.
• 优先队列默认是从大到小排序，因此需要重载运算符.

---

#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;
const int MAXN=1000010,MAXM=1000010;
struct Edge{int from,to,w,nxt;
}e[MAXM];
int head[MAXN],edgeCnt=1;
void addEdge(int u,int v,int w){e[++edgeCnt].from=u;e[edgeCnt].to=v;e[edgeCnt].w=w;e[edgeCnt].nxt=head[u];head[u]=edgeCnt;
}
int s;
struct Node{int nowPoint,dis;bool operator <(Node another)const{return dis>another.dis;}
};
int dis[MAXN];
void dijkstra(){priority_queue<Node> q;q.push(Node{s,0});dis[s]=0;while(!q.empty()){Node nowNode=q.top();q.pop();int nowPoint=nowNode.nowPoint,nowDis=nowNode.dis;if(nowDis>dis[nowPoint])continue;for(int i=head[nowPoint];i;i=e[i].nxt){int nowV=e[i].to;if(dis[nowPoint]+e[i].w<dis[nowV]){q.push(Node{nowV,dis[nowPoint]+e[i].w});dis[nowV]=dis[nowPoint]+e[i].w;}}}
}
const int INF=2e9;
int main(){int n,m;scanf("%d%d%d",&n,&m,&s);for(int i=1;i<=n;i++)dis[i]=INF;for(int i=1;i<=m;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);addEdge(u,v,w);}dijkstra();for(int i=1;i<=n;i++){printf("%d ",dis[i]);}printf("\n");return 0;
}

 

这篇关于P4779 【模板】单源最短路径的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---