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

題目背景

本題測(cè)試數(shù)據(jù)為隨機(jī)數(shù)據(jù)，在考試中可能會(huì)出現(xiàn)構(gòu)造數(shù)據(jù)讓SPFA不通過，如有需要請(qǐng)移步?P4779?https://www.luogu.com.cn/problemnew/show/P4779。

題目描述

如題，給出一個(gè)有向圖，請(qǐng)輸出從某一點(diǎn)出發(fā)到所有點(diǎn)的最短路徑長(zhǎng)度。

輸入格式

第一行包含三個(gè)整數(shù)N、M、S，分別表示點(diǎn)的個(gè)數(shù)、有向邊的個(gè)數(shù)、出發(fā)點(diǎn)的編號(hào)。

接下來M行每行包含三個(gè)整數(shù)Fi、Gi、Wi，分別表示第i條有向邊的出發(fā)點(diǎn)、目標(biāo)點(diǎn)和長(zhǎng)度。

輸出格式

一行，包含N個(gè)用空格分隔的整數(shù)，其中第i個(gè)整數(shù)表示從點(diǎn)S出發(fā)到點(diǎn)i的最短路徑長(zhǎng)度（若S=i則最短路徑長(zhǎng)度為0，若從點(diǎn)S無法到達(dá)點(diǎn)i，則最短路徑長(zhǎng)度為2147483647）

輸入輸出樣例

輸入 #1復(fù)制

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

輸出 #1復(fù)制

0 2 4 3

說明/提示

時(shí)空限制：1000ms,128M

數(shù)據(jù)規(guī)模：

對(duì)于20%的數(shù)據(jù)：N<=5，M<=15；

對(duì)于40%的數(shù)據(jù)：N<=100，M<=10000；

對(duì)于70%的數(shù)據(jù)：N<=1000，M<=100000；

對(duì)于100%的數(shù)據(jù)：N<=10000，M<=500000。保證數(shù)據(jù)隨機(jī)。

對(duì)于真正 100% 的數(shù)據(jù)，請(qǐng)移步?P4779。請(qǐng)注意，該題與本題數(shù)據(jù)范圍略有不同。

樣例說明：

圖片1到3和1到4的文字位置調(diào)換

2.思路

求最短路徑用Dijkstra算法：

迪杰斯特拉算法(Dijkstra)是由荷蘭計(jì)算機(jī)科學(xué)家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是從一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑算法，解決的是有權(quán)圖中最短路徑問題。迪杰斯特拉算法主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。

Dijkstra算法一般的表述通常有兩種方式，一種用永久和臨時(shí)標(biāo)號(hào)方式，一種是用OPEN, CLOSE表的方式，這里均采用永久和臨時(shí)標(biāo)號(hào)的方式。注意該算法要求圖中不存在負(fù)權(quán)邊。?[1]

問題描述

編輯在有向圖?G=(V,E) 中，假設(shè)每條邊 E[i] 的長(zhǎng)度為 w[i]，找到由頂點(diǎn) V0 到其余各點(diǎn)的最短值。?[1]

算法思想

編輯按路徑長(zhǎng)度遞增次序產(chǎn)生算法：把頂點(diǎn)集合V分成兩組：（1）S：已求出的頂點(diǎn)的集合（初始時(shí)只含有源點(diǎn)V0）（2）V-S=T：尚未確定的頂點(diǎn)集合將T中頂點(diǎn)按遞增的次序加入到S中，保證：（1）從源點(diǎn)V0到S中其他各頂點(diǎn)的長(zhǎng)度都不大于從V0到T中任何頂點(diǎn)的最短路徑長(zhǎng)度（2）每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)距離值S中頂點(diǎn)：從V0到此頂點(diǎn)的長(zhǎng)度T中頂點(diǎn)：從V0到此頂點(diǎn)的只包括S中頂點(diǎn)作中間頂點(diǎn)的最短路徑長(zhǎng)度依據(jù)：可以證明V0到T中頂點(diǎn)Vk的，或是從V0到Vk的直接路徑的權(quán)值；或是從V0經(jīng)S中頂點(diǎn)到Vk的路徑權(quán)值之和（反證法可證）求最短路徑步驟算法步驟如下：G={V,E}1. 初始時(shí)令 S={V0},T=V-S={其余頂點(diǎn)}，T中頂點(diǎn)對(duì)應(yīng)的距離值若存在<V0,Vi>，d(V0,Vi)為<V0,Vi>弧上的權(quán)值若不存在<V0,Vi>，d(V0,Vi)為∞2. 從T中選取一個(gè)與S中頂點(diǎn)有關(guān)聯(lián)邊且權(quán)值最小的頂點(diǎn)W，加入到S中3. 對(duì)其余T中頂點(diǎn)的距離值進(jìn)行修改：若加進(jìn)W作中間頂點(diǎn)，從V0到Vi的距離值縮短，則修改此距離值重復(fù)上述步驟2、3，直到S中包含所有頂點(diǎn)，即W=Vi為止

算法

堆優(yōu)化

思考

該算法復(fù)雜度為n^2,我們可以發(fā)現(xiàn)，如果邊數(shù)遠(yuǎn)小于n^2,對(duì)此可以考慮用堆這種數(shù)據(jù)結(jié)構(gòu)進(jìn)行優(yōu)化，取出最短路徑的復(fù)雜度降為O(1)；每次調(diào)整的復(fù)雜度降為O（elogn）；e為該點(diǎn)的邊數(shù)，所以復(fù)雜度降為O((m+n)logn)。

實(shí)現(xiàn)

1. 將源點(diǎn)加入堆，并調(diào)整堆。2. 選出堆頂元素u（即代價(jià)最小的元素），從堆中刪除，并對(duì)堆進(jìn)行調(diào)整。3. 處理與u相鄰的，未被訪問過的，滿足三角不等式的頂點(diǎn)1):若該點(diǎn)在堆里，更新距離，并調(diào)整該元素在堆中的位置。2):若該點(diǎn)不在堆里，加入堆，更新堆。4. 若取到的u為終點(diǎn)，結(jié)束算法；否則重復(fù)步驟2、3。

C++實(shí)現(xiàn) Dijkstra ：

#include<stdio.h>
#include<stdlib.h>
#define?max1?10000000??//原詞條這里的值太大，導(dǎo)致溢出，后面比較大小時(shí)會(huì)出錯(cuò)
int?a[1000][1000];
int?d[1000];//d表示源節(jié)點(diǎn)到該節(jié)點(diǎn)的最小距離
int?p[1000];//p標(biāo)記訪問過的節(jié)點(diǎn)
int?i,?j,?k;
int?m;//m代表邊數(shù)
int?n;//n代表點(diǎn)數(shù)
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;
//下面這個(gè)for循環(huán)的功能類似冒泡排序，目的是找到未訪問節(jié)點(diǎn)中d[j]值最小的那個(gè)節(jié)點(diǎn)，
//作為下一個(gè)訪問節(jié)點(diǎn)，用k標(biāo)記
for(j=1;j<=n;j++)
if(!p[j]&&d[j]<min1)
{
min1=d[j];
k=j;
}
//p[k]=d[k];?//?這是原來的代碼，用下一?條代碼替代。初始時(shí)，執(zhí)行到這里k=1，而d[1]=0
//從而p[1]等于0，這樣的話，上面的循環(huán)在之后的每次執(zhí)行之后，k還是等于1。
p[k]?=?1;?//置1表示第k個(gè)節(jié)點(diǎn)已經(jīng)訪問過了
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];
}
//最終輸出從源節(jié)點(diǎn)到其他每個(gè)節(jié)點(diǎn)的最小距離
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：