#C/C++#邻接表+SPFA单源最短路径算法模板

题目描述

如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。

输入输出格式

输入格式：

第一行包含三个整数N、M、S，分别表示点的个数、有向边的个数、出发点的编号。

接下来M行每行包含三个整数Fi、Gi、Wi，分别表示第i条有向边的出发点、目标点和长度。

输出格式：

一行，包含N个用空格分隔的整数，其中第i个整数表示从点S出发到点i的最短路径长度（若S=i则最短路径长度为0，若从点S无法到达点i，则最短路径长度为2147483647）

输入输出样例

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

本人提供的题解

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

const int maxm = 500002;
const int maxn = 10002;
const int INF = 2147483647;

struct Edge {
	int dis;
	int to;
	int next;
} edge[maxm]; 

int head[maxn];
int dis[maxn];
bool vis[maxn];
int cnt;

void add(int ,int ,int ); 

int main() {
	queue <int > Q;
	int n,m,s;
	scanf("%d%d%d",&n,&m,&s);
	for(int i = 1;i <= m;++i) {
		int f,t,d;
		scanf("%d%d%d",&f,&t,&d);
		add(f,t,d);
	}
	for(int i = 1;i <= n;++i)
		dis[i] = INF;
	dis[s] = 0;
	Q.push(s);
	vis[s] = true;
	while(!Q.empty()) {
		int u = Q.front();
		Q.pop();
		vis[u] = false;
		for(int i = head[u];i;i = edge[i].next) {
			int v = edge[i].to;
			if(dis[v] > dis[u] + edge[i].dis) {
				dis[v] = dis[u] + edge[i].dis;
				if(!vis[v]) {
					Q.push(v);
					vis[v] = true; 
				} 
			} 
		}
	}
	for(int i = 1;i <= n;++i)
		printf("%d ",dis[i]);
	return 0;
}
void add(int from,int to,int dis) {
	edge[++cnt].next = head[from];
	edge[cnt].to = to;
	edge[cnt].dis = dis;
	head[from] = cnt;
}