单源最短路径（弱化版）

题目

给出一个有向图，请输出从某一点出发到所有点的最短路径长度。

输入

第一行包含三个整数N、M、S，分别表示点的个数、有向边的个数、出发点的编号。
接下来M行每行包含三个整数Fi、Gi、Wi，分别表示第i条有向边的出发点、目标点和长度。

输出

一行，包含N个用空格分隔的整数，其中第i个整数表示从点S出发到点i的最短路径长度（若S=i则最短路径长度为0，若从点S无法到达点i，则最短路径长度为2147483647）

输出样例

4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

输出样例

0 2 4 3

数据范围

对于20%的数据：N<=5，M<=15；

对于40%的数据：N<=100，M<=10000；

对于70%的数据：N<=1000，M<=100000；

对于100%的数据：N<=10000，M<=500000。保证数据随机。

思路

其实这道题，就是一道最短路模板题。
我在这里用SPFA来做。

代码

#include<cstdio>
#include<iostream>
#include<cmath>
#include<queue>
using namespace std;
struct note
{
	int x,next,th;
}e[1000001];
int n,m,ls[10001],s,k,ii,jj,kk,an[10001];
bool in[10001];
int main()
{
	scanf("%d%d%d",&n,&m,&s);//读入
	for (int i=1;i<=n;i++) an[i]=2147483647;//枚举标记初值
	for (int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&ii,&jj,&kk);//读入
		e[++k]=(note){jj,ls[ii],kk};ls[ii]=k;//建邻接表
	}
	queue<int>l;//建队列
	an[s]=0;
	l.push(s);
	in[s]=1;
	while (!l.empty())//SPFA
	{
		int hh=l.front();
		l.pop();
		for (int i=ls[hh];i;i=e[i].next)
		if (an[e[i].x]>an[hh]+e[i].th)
		{
			an[e[i].x]=an[hh]+e[i].th;
			if (!in[e[i].x])
			{
				l.push(e[i].x);
				in[e[i].x]=1;
			}
		}
		in[hh]=0;
	}
	for (int i=1;i<=n;i++)
	if (i==s) printf("0 ");
	else printf("%d ",an[i]);//输出
	return 0;
}