题目描述
给定一个 nnn 个点，mmm 条有向边的带非负权图，请你计算从 sss 出发，到每个点的距离。
数据保证你能从 sss 出发到任意点。
输入格式
第一行为三个正整数 n,m,sn, m, sn,m,s。 第二行起 mmm 行，每行三个非负整数 ui,vi,wiu_i, v_i, w_iui,vi,wi，表示从 uiu_iui 到 viv_ivi 有一条权值为 wiw_iwi 的有向边。
输出格式
输出一行 nnn 个空格分隔的非负整数，表示 sss 到每个点的距离。
输入输出样例
输入 #1
4 6 1 1 2 2 2 3 2 2 4 1 1 3 5 3 4 3 1 4 4
输出 #1
0 2 4 3
#include<iostream>
#include<stdio.h>
#include<queue>
#include<algorithm>
#define WQD 2147483647
#define maxn 10000001
using namespace std;
struct VD
{
int v,d;
bool operator<(const VD&a)const
{ return a.d<d;
}
};
struct Edge
{
int to,w,next;
};
Edge edge[maxn];
int head[maxn],u,v,d,dis[maxn],m,n,S,num=0;
void add(int from,int to,int di)
{
edge[++num].next=head[from];
edge[num].to=to;
edge[num].w=di;
head[from]=num;
}
void dijkstra(int s)
{
priority_queue<VD>q;
for(int i=1;i<=n;i++) dis[i]=WQD;
dis[s]=0;
VD temp;
temp.d=dis[s];temp.v=s;
q.push(temp);
while(!q.empty())
{
temp=q.top();
q.pop();
int p=temp.v;
if(dis[p]<temp.d) continue;
for(int i=head[p];i!=0;i=edge[i].next)
if(dis[edge[i].to]>dis[p]+edge[i].w)
{
dis[edge[i].to]=dis[p]+edge[i].w;
temp.v=edge[i].to;temp.d=dis[edge[i].to];
q.push(temp);
}
}
return;
}
int main()
{
cin>>n>>m>>S;
for(int i=1;i<=m;i++)
{cin>>u>>v>>d;
add(u,v,d);
}
dijkstra(S);
for(int i=1;i<=n;i++)
cout<<dis[i]<<' ';
return 0;
}
单源最短路dijkstra算法模板；
void dijkstra(int s)
{
priority_queue<VD>q;
for(int i=1;i<=n;i++) dis[i]=WQD;
dis[s]=0;
VD temp;
temp.d=dis[s];temp.v=s;
q.push(temp);
while(!q.empty())
{
temp=q.top();
q.pop();
int p=temp.v;
if(dis[p]<temp.d) continue;
for(int i=head[p];i!=0;i=edge[i].next)
if(dis[edge[i].to]>dis[p]+edge[i].w)
{
dis[edge[i].to]=dis[p]+edge[i].w;
temp.v=edge[i].to;temp.d=dis[edge[i].to];
q.push(temp);
}
}
return;
}
用优先队列每次取最短的边遍历，优化时间；
if(dis[p]<temp.d) continue;
判断该temp对应的dis是否是该点最短路，若不是继续下一个点，减少遍历次数，优化了时间；