​
题目背景
本题测试数据为随机数据，在考试中可能会出现构造数据让SPFA不通过，如有需要请移步 P4779。

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

输入格式
第一行包含三个整数 n,m,sn,m,s，分别表示点的个数、有向边的个数、出发点的编号。

接下来 mm 行每行包含三个整数 u,v,wu,v,w，表示一条 u \to vu→v 的，长度为 ww 的边。

输出格式
输出一行 nn 个整数，第 ii 个表示 ss 到第 ii 个点的最短路径，若不能到达则输出 2^{31}-1231−1。

输入输出样例
输入 #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
说明/提示
【数据范围】
对于 20\%20% 的数据：1\le n \le 51≤n≤5，1\le m \le 151≤m≤15；
对于 40\%40% 的数据：1\le n \le 1001≤n≤100，1\le m \le 10^41≤m≤104；
对于 70\%70% 的数据：1\le n \le 10001≤n≤1000，1\le m \le 10^51≤m≤105；
对于 100\%100% 的数据：1 \le n \le 10^41≤n≤104，1\le m \le 5\times 10^51≤m≤5×105，1\le u,v\le n1≤u,v≤n，w\ge 0w≥0，\sum w< 2^{31}∑w<231，保证数据随机。

Update 2022/07/29：两个点之间可能有多条边，敬请注意。

对于真正 100\%100% 的数据，请移步 P4779。请注意，该题与本题数据范围略有不同。

样例说明：

图片1到3和1到4的文字位置调换

具体做法

include

include

include

include

include

include//队列头文件

using namespace std;
struct node{

int u,v,w,next; 

}e[1000001];
long long int ecnt=0;
long long int head[1010101];

long long int n,m,s;
void addedge(int u,int v,int w){

e[++ecnt].u=u;
e[ecnt].v=v;
e[ecnt].w=w;
e[ecnt].next=head[u];
head[u]=ecnt;

}
long long int dis[1010101],vis[1000001];
void spfa(){

for(int i=1;i<=n;i++){
    dis[i]=2147483647;//先将每一个点的距离设为最大值
}
queue<int>q;
q.push(s);//将出发点入队
dis[s]=0;//出发点到自身距离为0
while(!q.empty()){
    int x=q.front();//取出队首元素
    q.pop();//出队队首元素
    vis[x]=0;
    for(int i=head[x];i;i=e[i].next){//假设next记录的是3，2，1，0；所以当next为0的时候，循环就结束了，head时起点
        int v=e[i].v;
        if(dis[v]>dis[x]+e[i].w){//假设a，b,c,a->b=1,b->c=1,a->c=5，那么a-b-c的值要小于a-c，所以需要绕路
            dis[v]=dis[x]+e[i].w;
            if(!vis[v]){/如果这个点没走过
                vis[v]=1;
                q.push(v);//入队
            }
        }
    }
}

}
int main(){

cin>>n>>m>>s;
for(int i=1;i<=m;i++){
    int a,b,c;
    cin>>a>>b>>c;
    addedge(a,b,c);//记录数据
}
spfa();//开始处理
for(int i=1;i<=n;i++)
    cout<<dis[i]<<" ";

}
总结：这道题在做的时候需要注意数据范围，考虑是道模板题，所以梳理思路很重要；

​