APTX博客

  • ACGN
  • Coding
  • DevOps
  • Daily
  • Share
  • Bangumi
APTX Blog
A Moe Blog Set Up By ミズキ
  1. 首页
  2. OI
  3. 正文

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

2018年6月6日 1386点热度 0人点赞 0条评论

题目描述

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

输入输出格式

输入格式:

第一行包含三个整数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;
}

 

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可
标签: C/C++ C++ 图论 最短路
最后更新:2018年6月6日

神楽坂 みずき

萌萌萌,好萌!

点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

神楽坂 みずき

萌萌萌,好萌!

搜索
最新 热点 随机
最新 热点 随机
站点域名变更通知 私たちの居る理由 《サクラノ詩》VI 章 直哉与蓝对话 从《AMRITA》到《HELLO WORLD》── 野﨑まど世界观下的个体与世界的真实感 几种云端 VSCode/类 VSCode 方案对比与部署 Summer Pockets REFLECTION BLUE 豪華限定版 早期予約色紙付き/通販・店舗対応版
斐讯N1电视盒子推荐固件及常用软件分享 Linux中screen命令简略笔记 C/C++字符串哈希(单哈希)Hash算法 模板 2020/01/28:MMPI临床量表测量结果 #动漫#《烟花》观后感:莫名其妙的剧情 POJ 3233 Matrix Power Series(矩阵快速幂+二分)题解
标签聚合
洛谷 HTML 动漫 C++ C/C++ OI 日常 ST
分类
  • ACGN
  • Coding
  • Daily
  • DevOps
  • OI
  • Share

COPYRIGHT © 2017-2022 APTX博客. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang