题目背景
2018 年 7 月 19 日,某位同学在 NOI Day 1 T1 归程 一题里非常熟练地使用了一个广为人知的算法求最短路。
然后呢?
100→60
Ag→Cu
最终,他因此没能与理想的大学达成契约。
小 F 衷心祝愿大家不再重蹈覆辙。
题目描述
给定一个 N 个点,M 条有向边的带非负权图,请你计算从 S 出发,到每个点的距离。
数据保证你能从 S 出发到任意点。
输入输出格式
输入格式:
第一行为三个正整数 N,M,S。 第二行起 M 行,每行三个非负整数 ui,vi,wi,表示从 ui 到 vi 有一条权值为 wi的边。
输出格式:
输出一行 N 个空格分隔的非负整数,表示 S 到每个点的距离。
输入输出样例
输入样例#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
说明
样例解释请参考 数据随机的模板题。
1≤N≤100000;
1≤M≤200000;
S=1;
1≤ui,vi≤N;
0≤wi≤109,
0≤∑wi≤109。
—————————————————————————-
#include<cstdio>
#include<queue>
using namespace std;
int val[],dis[],vis[],head[],nxt[],to[];
int n,m,s,k;struct pot //结构体:x-顶点 dis-最短路径
{
int x,dis;
pot(int _x=,int _dis=):x(_x),dis(_dis){}
friend bool operator < (pot a,pot b)
{
return a.dis>b.dis; //改为大根堆
}
};
priority_queue<pot> que; //定义一个堆 void dijkstra() //定义dijkstra函数 (仅用一步不用递归递推什么的)
{
for(int i=;i<=n;i++) dis[i]=2e9; //初始值使所有点无穷大
que.push(pot(s,)); //s 出发点 自己到自己 距离为 0 同时也是最小值
dis[s]=;
while(!que.empty()) //循环一步 算s到一个点的最短路径
{
pot now;
now=que.top();
que.pop(); //取第一个边 并弹出
if(vis[now.x]) continue;
vis[now.x]=true; //标记已经访问过了
for(int i=head[now.x];i;i=nxt[i])
{
if(dis[to[i]]>dis[now.x]+val[i])
{
dis[to[i]]=dis[now.x]+val[i]; //更新最小值
que.push(pot(to[i],dis[to[i]])); //把新的压入堆中
}
}
}
}void add(int a,int b,int c) //一波加边的操作
{
k++; //给新加入的边编号
nxt[k]=head[a]; //新增的这条边k 紧挨着的是 之前a出发的第一条边(相当于把k边加到最上面)
to[k]=b; //k 这条边指向的点
val[k]=c; //边权值
head[a]=k; //head 从a点出发的第一条边
}int main()
{
int a,b,c;
scanf("%d%d%d",&n,&m,&s);
for(int i=;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
add(a,b,c); //加边
}
dijkstra();
for(int i=;i<=n;i++) printf("%d ",dis[i]);
return ;
}