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 出发，到每个点的距离。

数据保证你能从 S 出发到任意点。

输入格式

第一行为三个正整数 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。

本题数据可能会持续更新，但不会重测，望周知。

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循环输出
   return 0;      //不写return 0,成绩return 0
}

评测记录 in 2019-02-07

评测记录 in 2019-10-10