1.【題目鏈接】https://www.luogu.com.cn/problem/P4779，【弱化版】https://www.luogu.com.cn/problem/P4779

題目背景

2018 年 7 月 19 日，某位同學在?NOI Day 1 T1 歸程?一題里非常熟練地使用了一個廣為人知的算法求最短路。

然后呢？

100 \rightarrow 60100→60；

Ag \rightarrow CuAg→Cu；

最終，他因此沒能與理想的大學達成契約。

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

題目描述

給定一個?N 個點，M?條有向邊的帶非負權圖，請你計算從?S?出發(fā)，到每個點的距離。

數據保證你能從?S?出發(fā)到任意點。

輸入格式

第一行為三個正整數?N, M, S。 第二行起?M 行，每行三個非負整數?u_i, v_i, w_i，表示從?u_iui?到?v_i?有一條權值為?w_i?的邊。

輸出格式

輸出一行?N?個空格分隔的非負整數，表示?S?到每個點的距離。

輸入輸出樣例

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

說明/提示

樣例解釋請參考?數據隨機的模板題。

1 \leq N \leq 1000001≤N≤100000；

1 \leq M \leq 2000001≤M≤200000；

S = 1S=1；

1 \leq u_i, v_i\leq N1≤ui,vi≤N；

0 \leq w_i \leq 10 ^ 90≤wi≤109,

0 \leq \sum w_i \leq 10 ^ 90≤∑wi≤109。

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

2018.09.04 數據更新 from @zzq

2.思路

思路請看弱化版博客

傳送門??https://www.bilibili.com/read/cv4282019

3.Code

//Happynewyear 2019/2/7 18:21
#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 (re int i=1;i<=n;i++) printf("%d ? ? ?",dis[i]); ? ? ? ? ? //for循環(huán)輸出
? ?return 0; ? ? ?//不寫return 0,成績return 0
}

評測記錄 in 2019-02-07

評測記錄 in 2019-10-10