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;

}

巴特西

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

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

题目背景

题目描述

输入格式

输出格式

输入输出样例

说明/提示

【完整代码】

最新文章

热门文章

巴特西

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

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

题目背景

题目描述

输入格式

输出格式

输入输出样例

说明/提示

【完整代码】

最新文章

热门文章

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