本文主要是介绍neuq-acm预备队训练week 8 P4779 【模板】单源最短路径（标准版），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目背景
题目限制
题目描述
给定一个 n 个点，m 条有向边的带非负权图，请你计算从 s 出发，到每个点的距离。
数据保证你能从 s 出发到任意点。
输入格式
第一行为三个正整数n,m,s。 第二行起 m 行，每行三个非负整数 ui,vi,wi，表示从 ui 到 vi 有一条权值为 wi 的有向边。
输出格式
输出一行 n 个空格分隔的非负整数，表示 s 到每个点的距离。
输入输出样例
解题思路
本题应使用单源最短路算法——Dijkstra算法。还要用优先队列，要找最小的点，所以用优先队列时还需要重载运算符
AC代码
#include <bits/stdc++.h>
using namespace std;
#define inf 0x7FFFFFFF
#define qj 1000000
struct Edge
{int next;int to;int wei;
}edge[qj];
struct priority
{int ans;int id;bool operator <(const priority &x)const{return x.ans<ans;}
};
int n,m,s,cnt;
int V[qj];
int head[qj];
long long ans[qj];
void add(int x,int y,int z);
priority_queue<priority> q;
int main()
{int u,v,w;cin>>n>>m>>s;for(int i=1;i<=m;i++){ans[i]=inf;}memset(V,0,sizeof(V));ans[s]=0;for(int i=1;i<=m;i++){cin>>u>>v>>w;add(u,v,w);}int pos;q.push((priority){0,s});while(!q.empty()){priority temp=q.top();q.pop();pos=temp.id;if(!V[pos]){V[pos]=1;for(int i=head[pos];i;i=edge[i].next){int v=edge[i].to;if(ans[v]>ans[pos]+edge[i].wei){ans[v]=ans[pos]+edge[i].wei;if(!V[v]){q.push((priority){ans[v],v});}}}}}for(int i=1;i<=n;i++)cout<<ans[i]<<' ';return 0;
}void add(int x,int y,int z)
{edge[++cnt].to=y;edge[cnt].wei=z;edge[cnt].next=head[x];head[x]=cnt;
}
这篇关于neuq-acm预备队训练week 8 P4779 【模板】单源最短路径（标准版）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
