欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

单源最短路径(弱化版)

程序员文章站 2024-01-14 16:52:10
...

##题目大意:
给出一个有向图,请输出从S出发到所有点的最短路径长度。

##解题思路:
看到数据范围 Spfa
然后莫名尴尬地WA了一个点
我就把inf 1000000000 改为 2147483647
发现dis会炸掉,于是把dis改成了long long,保险起见,inf 也改成了long long

看H*B的码风,我打算试一试,发现并不爽,但是我懒得改

##Accepted code:
####献上本蒟蒻的标风代码:

#include <bits/stdc++.h>

using namespace std;

const int inf = 1000000000;
struct node {
	int to, z, next;
}e[200001];
int last[100001], dis[100001], n, m, S, cnt;
bool v[100001];

inline void Add(int x, int y, int z) {
	e[++cnt].to = y; e[cnt].z = z; e[cnt].next = last[x]; last[x] = cnt;
}

void Spfa() {
	dis[S] = 0; v[S] = 1;
	queue <int> q;
	q.push(S);
	while (q.size()) {
		int x = q.front(); v[x] = 0; q.pop();
		for (int i = last[x]; i; i = e[i].next) {
			int y = e[i].to;
			if (dis[y] > dis[x] + e[i].z) {
				dis[y] = dis[x] + e[i].z;
				if (!v[y]) {
					q.push(y);
					v[y] = 1;
				}
			}
		}
	}
}

int main() {
	scanf("%d%d%d", &n, &m, &S);
	for (int i = 1; i <= m; i++) {
		int x, y, z; scanf("%d%d%d", &x, &y, &z);
		Add(x, y, z);
	}
	for (int i = 1; i <= n; i++) dis[i] = inf;
	Spfa();
	for (int i = 1; i <= n; i++) printf("%d ", dis[i]);
}