P4779 【模板】单源最短路径（标准版）

题目背景

2018 年 7 月 19 日，某位同学在 NOI Day 1 T1 归程一题里非常熟练地使用了一个广为人知的算法求最短路。

然后呢？

100 \rightarrow 60100→60；

Ag \rightarrow CuAg→Cu；

最终，他因此没能与理想的大学达成契约。

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

题目描述

给定一个 NN 个点，MM 条有向边的带非负权图，请你计算从 SS 出发，到每个点的距离。

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

输入格式

第一行为三个正整数 N, M, SN,M,S。第二行起 MM 行，每行三个非负整数 u_i, v_i, w_iui,vi,wi，表示从 u_iui 到 v_ivi 有一条权值为 w_iwi 的边。

输出格式

输出一行 NN 个空格分隔的非负整数，表示 SS 到每个点的距离。

输入输出样例

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

【完整代码】

#include<iostream>
#include<cstdio>
#include<queue>

using namespace std;
struct point
{
    int w;//路径的长度
    int x;//点的标号
    bool operator < (const point & xx)const//重载运算符
    {
        return xx.w < w;
    }
};
priority_queue<point>q;//保证每次都拿最小的路径来更新
const int Max = 400005;
struct node
{
    int y,z;
    int ne;
}a[Max];
int sum = 0;
int n,m,s;
int head[Max >> 2];

void add(int x,int y,int z)//插入邻接矩阵
{
    a[++ sum].y = y;
    a[sum].ne = head[x];
    a[sum].z = z;
    head[x] = sum;
}
int dis[Max >> 2];
bool use[Max >> 2];

void dj()
{
    dis[s] = 0;//自己到自己的距离为0
    q.push((point){0,s});
    while(!q.empty())
    {
        point qwq = q.top();
        q.pop();
        int x = qwq.x,w = qwq.w;
        if(use[x] == true)//没个点只能用来更新一次
            continue;//不放进去也没有办法更新
        else
            use[x] = true;
        for(register int i = head[x];i != 0;i = a[i].ne)
        {
            int awa = a[i].y;
            if(dis[awa] > dis[x] + a[i].z)//松弛操作
            {
                dis[awa] = dis[x] + a[i].z;//更新
                if(use[awa] == false)//没有入队
                    q.push((point){dis[awa],awa});//入队
            }
        }
    }
}

int main()
{
    int x,y,z;
    scanf("%d%d%d",&n,&m,&s);
    for(register int i = 1;i <= n;++ i)
        dis[i] = 0x7fffffff;//赋值一个极大数
    for(register int i = 1;i <= m;++ i)
    {
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
    }
    dj();
    for(register int i = 1;i <= n;++ i)
        cout << dis[i] << " ";
    return 0;
}

i​

洛谷 P4779 【模板】单源最短路径（标准版） 题解