P3371 【模板】单源最短路径

题目描述

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

输入输出格式

输入格式：

第一行包含三个整数N、M、S，分别表示点的个数、有向边的个数、出发点的编号。

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

输出格式：

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

输入输出样例

输入样例#1：

输出样例#1：

0 2 4 3

说明

时空限制：1000ms,128M

数据规模：

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

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

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

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

样例说明：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<queue>

 using namespace std;

 const int MAXN=;

 struct node

 {

     int u;

     int v;

     int w;

     int next;

 }edge[MAXN];

 int num=;

 int head[MAXN];

 void add(int x,int y,int z)

 {

     edge[num].u=x;

     edge[num].v=y;

     edge[num].w=z;

     edge[num].next=head[x];

     head[x]=num++;

 }

 int dis[MAXN];

 int vis[MAXN];

 int n,m,s;

 void SPFA(int s)

 {

     dis[s]=;

     vis[s]=;

     queue<int>q;

     q.push(s);

     while(q.size()!=)

     {

         int p=q.front();

         q.pop();

         vis[p]=;

         for(int i=head[p];i!=-;i=edge[i].next)

         {

             int to=edge[i].v;

             if(dis[to]>dis[p]+edge[i].w)

             {

                 dis[to]=dis[p]+edge[i].w;

                 if(vis[to]==)

                 {

                     q.push(to);

                     vis[to]=;

                 }

             }

         }

     }

     for(int i=;i<=n;i++)

     {

         printf("%d ",dis[i]);

     }

 }

 int main()

 {

     scanf("%d%d%d",&n,&m,&s);

     for(int i=;i<=n;i++)head[i]=-,dis[i]=;

     for(int i=;i<=m;i++)

     {

         int x,y,z;

         scanf("%d%d%d",&x,&y,&z);

         add(x,y,z);

     }

     SPFA(s);

     return ;

 }

巴特西

P3371 【模板】单源最短路径

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章