# 【模板】單源最短路徑（標(biāo)準(zhǔn)版）

## 題目背景

2018 年 7 月 19 日，某位同學(xué)在 [NOI Day 1 T1 歸程](https://www.luogu.org/problemnew/show/P4768) 一題里非常熟練地使用了一個(gè)廣為人知的算法求最短路。

然后呢？

$100 \rightarrow 60$；

$\text{Ag} \rightarrow \text{Cu}$；

最終，他因此沒能與理想的大學(xué)達(dá)成契約。

小 F 衷心祝愿大家不再重蹈覆轍。

## 題目描述

給定一個(gè) $n$ 個(gè)點(diǎn)，$m$ 條有向邊的帶非負(fù)權(quán)圖，請(qǐng)你計(jì)算從 $s$ 出發(fā)，到每個(gè)點(diǎn)的距離。

數(shù)據(jù)保證你能從 $s$ 出發(fā)到任意點(diǎn)。

## 輸入格式

第一行為三個(gè)正整數(shù) $n, m, s$。
第二行起 $m$ 行，每行三個(gè)非負(fù)整數(shù) $u_i, v_i, w_i$，表示從 $u_i$ 到 $v_i$ 有一條權(quán)值為 $w_i$ 的有向邊。

## 輸出格式

輸出一行 $n$ 個(gè)空格分隔的非負(fù)整數(shù)，表示 $s$ 到每個(gè)點(diǎn)的距離。

## 樣例 #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
```

## 提示

樣例解釋請(qǐng)參考 [數(shù)據(jù)隨機(jī)的模板題](https://www.luogu.org/problemnew/show/P3371)。

$1 \leq n \leq 10^5$；

$1 \leq m \leq 2\times 10^5$；

$s = 1$；

$1 \leq u_i, v_i\leq n$；

$0 \leq w_i \leq 10 ^ 9$,

$0 \leq \sum w_i \leq 10 ^ 9$。

本題數(shù)據(jù)可能會(huì)持續(xù)更新，但不會(huì)重測，望周知。

2018.09.04 數(shù)據(jù)更新 from @zzq

1.這個(gè)問題用dijkstra算法即可，要使用堆優(yōu)化的dijkstra算法，否則會(huì)時(shí)間超限。

2.剛開始我是想自己手寫一個(gè)堆，模擬優(yōu)先隊(duì)列，然而修修改改還是只是AC了倆個(gè)點(diǎn) ，沒辦法去學(xué)了C++里面的STL里的優(yōu)先隊(duì)列。

3.繼而就簡單多了（代碼少了將近一大半）

4.堆優(yōu)化的dijkstra算法也是非常簡單，核心思想是一樣的，先松弛，再找最近的那一個(gè)點(diǎn)，繼續(xù)松弛循環(huán)下去。用堆來實(shí)現(xiàn)就是把新更新的距離權(quán)值入隊(duì)，然后在優(yōu)先隊(duì)列里面會(huì)自動(dòng)在首元素是最小值了。我們只需要判斷堆頂元素是否訪問過即可，如果訪問過了，就彈出堆頂元素，繼續(xù)找就可以。

while( !q.empty() )//如果隊(duì)列不為空，就需要繼續(xù)訪問{tmp = q.top();//訪問堆頂元素q.pop();//彈出隊(duì)頭x = tmp.pos, w = tmp.w;if( book[x] )continue;//如果該點(diǎn)已經(jīng)納入最短路徑，需要跳過book[x] = 1;//從該點(diǎn)開始松弛for(i = head[x]; i; i = e[i].next )//鏈?zhǔn)角跋蛐莧y = e[i].to;if( dis[y] > dis[x] + e[i].w ){dis[y] = dis[x] + e[i].w;if( !book[y] ){q.push( ( node ){dis[y], y} );//插入元素并且重新排序}}}}

完整C++代碼如下：

#include<iostream> #include<bits/stdc++.h> #include<cstdio> #include<algorithm>using namespace std;const int N = 100010, M = 500010; const int INF=1000000000; struct edges {int to;int w;int next; }e[M]; int head[N], dis[N]; bool book[N]; int n, m, s; struct node {int w;int pos;bool operator <( const node &x )const{return x.w <w;} }; priority_queue<node> q;//建立堆 void dijk() {int i,y,x,w;node tmp;dis[s] = 0;q.push( ( node ){0, s} );//放入該節(jié)點(diǎn)，也就是入隊(duì)while( !q.empty() )//如果隊(duì)列不為空，就需要繼續(xù)訪問{tmp = q.top();//訪問堆頂元素q.pop();//彈出隊(duì)頭x = tmp.pos, w = tmp.w;if( book[x] )continue;//如果該點(diǎn)已經(jīng)納入最短路徑，需要跳過book[x] = 1;//從該點(diǎn)開始松弛for(i = head[x]; i; i = e[i].next )//鏈?zhǔn)角跋蛐莧y = e[i].to;if( dis[y] > dis[x] + e[i].w ){dis[y] = dis[x] + e[i].w;if( !book[y] ){q.push( ( node ){dis[y], y} );//插入元素并且重新排序}}}}for( i = 1; i <= n; i++ )printf( "%d ", dis[i] ); } int main() {int i,u,v,w;scanf( "%d%d%d", &n, &m, &s );for(i = 1; i <= n; i++) dis[i] =INF;for(i = 1; i <= m; i++){scanf( "%d%d%d", &u, &v, &w );e[i].to=v;e[i].w=w;e[i].next=head[u];head[u]=i;}dijk();return 0; }

總結(jié)

以上是生活随笔為你收集整理的P4779 【模板】单源最短路径（标准版）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。