Description
2018 年 7 月 19 日，某位同学在 NOI Day 1 T1 归程 一题里非常熟练地使用了一个广为人知的算法求最短路。
然后呢？
100→60；
Ag→Cu；
最终，他因此没能与理想的大学达成契约。
小 F 衷心祝愿大家不再重蹈覆辙。
题目描述
给定一个 N 个点， M 条有向边的带非负权图，请你计算从 S 出发，到每个点的距离。
数据保证你能从 S 出发到任意点。
Input
第一行为三个正整数 N,M,S 。 第二行起 M 行，每行三个非负整数 ui,vi,wi ，表示从 ui 到 vi 有一条权值为 wi 的边。
Output
输出一行 N 个空格分隔的非负整数，表示 S 到每个点的距离。
Sample Input
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
Sample Output
0 2 4 3
Hint
样例解释请参考 数据随机的模板题。
1 ≤ N ≤ 100000；
1 ≤ M ≤ 200000；
S=1；
1 ≤ ui , vi ≤ N ；
0 ≤ wi ≤ 1e9 ,
0 ≤ ∑ wi ≤ 1e9 。
题解
8012年7月19日，SPFA终于还是迎来了被官方审判的日子。
SPFA的光辉 梦幻般消逝。
以前从来没写过堆优dijkstra，SPFA这么香用什么堆优
会了重载运算符之后回头看 发现比以前想象的好写了很多。
反正这就是道模板题。
SPFA很好卡这事大家都知道 但是SPFA真是香了这么多年
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
#define R register
inline int read()
{
char ch=getchar();
int x=0;
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x;
}
struct emm{
int e,f,v;
}a[200007];
int h[100007];
int n,m,s;
void scan()
{
n=read(),m=read(),s=read();
for(R int i=1;i<=m;++i)
{
int u=read(),v=read(),w=read();
a[i].f=h[u];
h[u]=i;
a[i].e=v;
a[i].v=w;
}
return;
}
struct ahh{
int dis,cod;
}aa;
struct cmp{
bool operator()(ahh qaq,ahh qwq){
return qaq.dis>qwq.dis;
}
};
priority_queue<ahh,vector<ahh>,cmp>q;
int d[100007];
bool sf[100007];
void dijkstra()
{
memset(d,127,sizeof(d));
d[s]=0;q.push((ahh){0,s});
while(!q.empty())
{
int x;
do{x=q.top().cod;q.pop();}while(sf[x]&&!q.empty());
sf[x]=1;
for(R int i=h[x];i;i=a[i].f)
if(d[a[i].e]>d[x]+a[i].v)
{
d[a[i].e]=d[x]+a[i].v;
if(!sf[a[i].e])q.push((ahh){d[a[i].e],a[i].e});
}
}
for(R int i=1;i<=n;++i)
printf("%d ",d[i]);
return;
}
int main()
{
scan();
dijkstra();
return 0;
}