1.【题目链接】https://www.luogu.com.cn/problemnew/show/P1427

题目背景

本题测试数据为随机数据，在考试中可能会出现构造数据让SPFA不通过，如有需要请移步 P4779 https://www.luogu.com.cn/problemnew/show/P4779。

题目描述

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

输入格式

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

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

输出格式

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

输入输出样例

输入 #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

说明/提示

时空限制：1000ms,128M

数据规模：

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

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

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

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

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

样例说明：

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

2.思路

求最短路径用Dijkstra算法：

迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

Dijkstra算法一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。 [1]

问题描述

编辑在有向图 G=(V,E) 中，假设每条边 E[i] 的长度为 w[i]，找到由顶点 V0 到其余各点的最短值。 [1]

算法思想

编辑按路径长度递增次序产生算法：把顶点集合V分成两组：（1）S：已求出的顶点的集合（初始时只含有源点V0）（2）V-S=T：尚未确定的顶点集合将T中顶点按递增的次序加入到S中，保证：（1）从源点V0到S中其他各顶点的长度都不大于从V0到T中任何顶点的最短路径长度（2）每个顶点对应一个距离值S中顶点：从V0到此顶点的长度T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度依据：可以证明V0到T中顶点Vk的，或是从V0到Vk的直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和（反证法可证）求最短路径步骤算法步骤如下：G={V,E}1. 初始时令 S={V0},T=V-S={其余顶点}，T中顶点对应的距离值若存在<V0,Vi>，d(V0,Vi)为<V0,Vi>弧上的权值若不存在<V0,Vi>，d(V0,Vi)为∞2. 从T中选取一个与S中顶点有关联边且权值最小的顶点W，加入到S中3. 对其余T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值缩短，则修改此距离值重复上述步骤2、3，直到S中包含所有顶点，即W=Vi为止

算法

堆优化

思考

该算法复杂度为n^2,我们可以发现，如果边数远小于n^2,对此可以考虑用堆这种数据结构进行优化，取出最短路径的复杂度降为O(1)；每次调整的复杂度降为O（elogn）；e为该点的边数，所以复杂度降为O((m+n)logn)。

实现

1. 将源点加入堆，并调整堆。2. 选出堆顶元素u（即代价最小的元素），从堆中删除，并对堆进行调整。3. 处理与u相邻的，未被访问过的，满足三角不等式的顶点1):若该点在堆里，更新距离，并调整该元素在堆中的位置。2):若该点不在堆里，加入堆，更新堆。4. 若取到的u为终点，结束算法；否则重复步骤2、3。

C++实现 Dijkstra ：

#include<stdio.h>
#include<stdlib.h>
#define max1 10000000  //原词条这里的值太大，导致溢出，后面比较大小时会出错
int a[1000][1000];
int d[1000];//d表示源节点到该节点的最小距离
int p[1000];//p标记访问过的节点
int i, j, k;
int m;//m代表边数
int n;//n代表点数
int main()
{
scanf("%d%d",&n,&m);
int    min1;
int    x,y,z;
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
a[x][y]=z;
a[y][x]=z;
}
for( i=1; i<=n; i++)
d[i]=max1;
d[1]=0;
for(i=1;i<=n;i++)
{
min1 = max1;
//下面这个for循环的功能类似冒泡排序，目的是找到未访问节点中d[j]值最小的那个节点，
//作为下一个访问节点，用k标记
for(j=1;j<=n;j++)
if(!p[j]&&d[j]<min1)
{
min1=d[j];
k=j;
}
//p[k]=d[k]; // 这是原来的代码，用下一 条代码替代。初始时，执行到这里k=1，而d[1]=0
//从而p[1]等于0，这样的话，上面的循环在之后的每次执行之后，k还是等于1。
p[k] = 1; //置1表示第k个节点已经访问过了
for(j=1;j<=n;j++)
if(a[k][j]!=0&&!p[j]&&d[j]>d[k]+a[k][j])
d[j]=d[k]+a[k][j];
}
//最终输出从源节点到其他每个节点的最小距离
for(i=1;i<n;i++)
printf("%d->",d[i]);
printf("%d\n",d[n]); 
return 0;
}

3.Code

//Happynewyear 2019/2/7 18:06
#include<bits/stdc++.h>
#define re register
using namespace std;

inline int read()
{
   int X=0,w=1; char c=getchar();
   while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
   while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
   return X*w;
}

struct Edge { int v,w,nxt; };
Edge e[500010];
int head[100010],cnt=0;

inline void addEdge(int u,int v,int w)
{
   e[++cnt].v=v;
   e[cnt].w=w;
   e[cnt].nxt=head[u];
   head[u]=cnt;
}

int n,m,s;
int dis[100010];

struct node
{
   int u,d;
   bool operator <(const node& rhs) const {
       return d>rhs.d;
   }
};

inline void Dijkstra() {
   for (re int i=1;i<=n;i++) dis[i]=2147483647;
   dis[s]=0;
   priority_queue<node> Q;
   Q.push((node){s,0});
   while (!Q.empty())
   {
       node fr=Q.top(); Q.pop();
       int u=fr.u,d=fr.d;
       if (d!=dis[u]) continue;
       for (re int i=head[u];i;i=e[i].nxt)
       {
           int v=e[i].v,w=e[i].w;
           if (dis[u]+w<dis[v])
           {
               dis[v]=dis[u]+w;
               Q.push((node){v,dis[v]});
           }
       }
   }
}

int main()
{
   n=read(),m=read(),s=read();
   for (re int i=1;i<=m;i++)
   {
       int X=read(),Y=read(),Z=read();
       addEdge(X,Y,Z);
   }
   Dijkstra();
   for(int i=1;i<=n;i++) printf("%d ",dis[i]);
   return 0;
}


提交记录 in 2019-02-07：

提交记录 in 2019-10-10：