蓝桥杯 算法提高 道路和航路 Djkstra + 拓扑序-程序员宅基地

一、内容

问题描述

农夫约翰正在针对一个新区域的牛奶配送合同进行研究。他打算分发牛奶到T个城镇(标号为1..T),这些城镇通过R条标号为(1..R)的道路和P条标号为(1..P)的航路相连。

每一条公路i或者航路i表示成连接城镇Ai(1<=A_i<=T)和Bi(1<=Bi<=T)代价为Ci。每一条公路,Ci的范围为0<=Ci<=10,000;由于奇怪的运营策略,每一条航路的Ci可能为负的,也就是-10,000<=Ci<=10,000。

每一条公路都是双向的,正向和反向的花费是一样的,都是非负的。

每一条航路都根据输入的Ai和Bi进行从Ai->Bi的单向通行。实际上,如果现在有一条航路是从Ai到Bi的话,那么意味着肯定没有通行方案从Bi回到Ai。

农夫约翰想把他那优良的牛奶从配送中心送到各个城镇,当然希望代价越小越好,你可以帮助他嘛?配送中心位于城镇S中(1<=S<=T)。
输入格式

输入的第一行包含四个用空格隔开的整数T,R,P,S。

接下来R行,描述公路信息,每行包含三个整数,分别表示Ai,Bi和Ci。

接下来P行,描述航路信息,每行包含三个整数,分别表示Ai,Bi和Ci。
输出格式
输出T行,分别表示从城镇S到每个城市的最小花费,如果到不了的话输出NO PATH。

样例输入

6 3 3 4
1 2 5
3 4 5
5 6 10
3 5 -100
4 6 -100
1 3 -10

样例输出

NO PATH
NO PATH
5
0
-95
-100

数据规模与约定

对于20%的数据,T<=100,R<=500,P<=500;

对于30%的数据,R<=1000,R<=10000,P<=3000;

对于100%的数据,1<=T<=25000,1<=R<=50000,1<=P<=50000。

二、思路

  • 由于道路是双向的(非负),而航线是单向(可能为负,但是航线没有回路)。 那么我们可以按照道路相连的点划分为几个连通块 。航线就是连接各个连通块的边,根据题目描述,这些连通块符合拓扑序。
  • 由于每个连通块内部的点都是道路相连(道路非负),那么我们可以在连通块内部求一次djkstra。按照拓扑序的顺序对每个连通块求解一次djkstra。按照拓扑序的顺序对每个连通块求最短路,这样就可以在求某个连通块时,其他连通块若能到达这个块,那么必然起点到其他点的最短路已经求好了,符合航线不构成回路的设定。

三、代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <iostream>
using namespace std;
const int N = 25005, M = 150005, INF = 0x3f3f3f3f;
struct E {
    
	int v, next, w;
} e[M];
struct Node {
    
	int dis, v;
	Node(int d, int v):dis(d), v(v){
    }
	bool operator < (const Node & w) const {
    
		return dis > w.dis;
	} 
};
int n, mr, mp, s, u, v, w, len = 1, head[N], d[N], id[N], in[N], cnt; 
//id记录这个点属于哪个连通块 cnt记录连通块的个数  in记录连通块的入度 
vector<int> b[N]; //记录某个连通块里面的所有点 
queue<int> q;
bool vis[N];
void add(int u, int v, int w) {
    
	e[len].v = v;
	e[len].w = w;
	e[len].next = head[u];
	head[u] = len++;
}
void dfs(int u, int bid) {
    
	id[u] = bid;
	b[bid].push_back(u); //将这个点放入这个连通块
	for (int j = head[u]; j; j = e[j].next) {
    
		int v = e[j].v;
		if (!id[v]) dfs(v, bid); //代表还没访问过 那么dfs一下 
	} 
}
void djkstra(int bid) {
    
	priority_queue<Node> pq;
	for (int i = 0; i < b[bid].size(); i++) {
    
		//将这个连通块内部的所有点入优先队列(因为不知道从哪里作为起点)
		int v = b[bid][i];
		pq.push(Node(d[v], v)); 
	}
	while (!pq.empty()) {
    
		int u = pq.top().v;
		pq.pop();
		if (vis[u]) continue;
		vis[u] = true;
		for (int j = head[u]; j; j = e[j].next) {
    
			int v = e[j].v;
			int w = e[j].w;
			if (d[v] > d[u] + w) {
    
				d[v] = d[u] + w;
				if (id[v] == id[u]) pq.push(Node(d[v], v)); //如果在這個连通块里面才入队 因为我们求的是在这个连通块里面的最短路
			}
			//注意q中保存的是连通块的id 
			if (id[v] != id[u] && (--in[id[v]]) == 0) q.push(id[v]); //可能连接连通块的其他边 那么就入度减少 
		} 
	} 
} 
void topsort() {
    
	memset(d, 0x3f, sizeof(d));
	d[s] = 0; //起点设置为0 
	//将入度为0的加入队列 
	for (int i = 1; i <= cnt; i++) if(!in[i]) q.push(i);
	while (!q.empty()) {
    
		int u = q.front();
		q.pop();
		djkstra(u); //每个连通块内部求解一次最短路 
	} 
}
int main() {
    
	scanf("%d%d%d%d", &n, &mr, &mp, &s);
	for (int i = 1; i <= mr; i++) {
    
		scanf("%d%d%d", &u, &v, &w);
		add(u, v, w); 
		add(v, u, w); 
	}
	//求出连通块的个数
	for (int i = 1; i <= n; i++) {
    
		if (!id[i]) dfs(i, ++cnt);
	} 
	//输入航线
	for (int i = 1; i <= mp; i++) {
    
		scanf("%d%d%d", &u, &v, &w);
		add(u, v, w);
		in[id[v]]++;//v所在的连通块的入度++ 
	} 
	topsort(); //进行拓扑序 求解每个连通块内部的最短路
	for (int i = 1; i <= n; i++) {
    
		if (d[i] > INF / 2) printf("NO PATH\n");
		else printf("%d\n", d[i]);
	} 
	return 0;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_41280600/article/details/104109781

智能推荐

如何在ModelArt运行深度学习案例-程序员宅基地

如何在ModelArt运行深度学习案例一、准备数据集和源代码本次所选案例是“基于ResNet50实现毒蘑菇识别实战”:学习视频:21天深度学习实战营 | 基于ResNet50实现毒蘑菇识别实战_哔哩哔哩_bilibili源码:mindspore-21-days-tutorials/chapter3 at main · mindspore-ai/mindspore-21-days-tutorials · GitHub案例学习PPT:百度网盘 请输入提取码提取码:eqbp_modelart

html与css基础知识小汇总,完善版1-程序员宅基地

标记语言:html特点:本身只能被读取,本身不具有行为能力和逻辑能力脚本语言:javascript,本身具有逻辑能力和行为能力,需要js的解析器解析执行例:console.log(1+1);//2编译语言:java 本身开始具有逻辑能力和行为能力,需编译运行例:system.out.print(1+1);//2html:注释 ctrl + /核心属性: id唯一标识class标识一类元素title描述信息style 样式元素分类1.块级元素:独占一行,用于结构的布局;可设置宽

hbase修复.META.表与HDFS文件不一致问题-程序员宅基地

在实际环境中遇到hbase fbck检查报hdfs数据块与META表信息不一致的错误。表现就是数据写入无法进行。 经过检查,发现在.META.表中对应的一些region块的子列少了regioninfo这一列;同时在hdfs的出错region文件夹下查看发现本来该是.regioninfo的文件夹变成了.tmp文件夹。在网上查了些资料,发现是region做分裂的时候失败,导致region

盘点数据处理工具,手把手教你做数据清洗和转换_大数据v的博客-程序员宅基地

导读:原始数据本身没有用。为了使它实际有用,你需要准备它。作者:Mars Geldard, Jonathon Manning, Paris Buttfield-Addison, Tim N..._清洗数据会用到那些大数据工具

中小企业信用与应收账款管理(转)-程序员宅基地

◆◇ 专家坐堂(主题:中小企业信用与应收账款管理) 提问内容: 提问人:cherry 提问时间:2007-06-19 14:18:33.0 回答内容:..._如何改善账款dso

随便推点

Webpack的习题_webpack选择题-程序员宅基地

1.grunt、webpack和gulp三个构建工具中,其中( )是任务流工具2( )是模块打包工具。(A)A.grunt和gulp,webpackB.webpack, grunt和gulpC.webpack和grunt,gulpC.gulp,webpack和grunt2.下列关于常见的Loader的描述中有误的是(C)A.source-map-loader:加载额外的 Source Map 文件,以方便断点调试B.image-loader:加载并且压缩图片文件C.style-loader_webpack选择题

Spring3, Hibernate3.6与Proxool连接池配置-程序员宅基地

鉴于Spring3.0不采用Servlet启动,改用listener,并且针对Mysql与DBCP连接池在linux服务器上超时连接的Bug,现简要地做Spring3与Proxool连接池的配置: 1.Web.xml配置:Java代码 xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" ve

【学习笔记】关于胡牌算法的一些小记-程序员宅基地

目前公司项目对于胡牌算法有一定的优化需求,对于新进公司的我来说是一个很好的锻炼机会,既可以依此熟悉公司项目代码,又可以增进自己对于技术的一些了解,这是前提。(描述的不对的地方还望斧正)由于对于棋牌类的游戏并不是特别了解,遂在网络上查找了很多算法,解决方案大致分为两种:1.DFS递归检测牌型 优点:通用性高,大部分麻将规则都可以不经过修改代码直接使用到项目中,面对常见牌型效率较高。 缺点...

DDR4内存全景解析_同样d4的内存条防呆口不一样-程序员宅基地

从SDRAM到DDR、再到DDR2、再到目前的DDR3,每一代内存都要横跨多代PC平台。当前主流的DDR3内存规范于2007年6月由JEDEC确定,经过长时间的发展,DDR3已经彻底取代了前代产品DDR2,成为市场主流。在5年后的2012年下半年,JEDEC又发布了新的DDR4规范,DDR4也将像DDR3取代DDR2那样,慢慢走入我们的PC,成为未来PC的最主流内存规范。那么DDR4有哪些优异特性_同样d4的内存条防呆口不一样

数据存储技术 - 林康平_喝醉酒的小白的博客-程序员宅基地

第7章 SAN技术介绍Storage Area Network7.1 SAN存储基础DAS -ICT - 信息通信LANHBA - Host Bus Adapter交换机网桥集线器网关FC接口 - FC协议ETH接口 - iSCSI协议FCoE接口 - FCoE协议7.2 FC SANFibre Channel - 光纤通道协议7.3 IP SANIP协议7.4 FCoE7.5 本章小结...

metal(四)大批量顶点数据的加载-程序员宅基地

针对setVertexBytes(:length:index:)方法在苹果的官方文档中有如下说明对于小于4KB(即4096字节)的一次性数据,使用setVertexBytes(:length:index:),如果数据长度超过4KB 或者需要多次使用顶点数据时,需要创建一个MTLBuffer对象,创建的buffer的目的就是为了将顶点数据存储到顶点缓存区,GPU可以直接访问该缓存区获取顶点数据,并且buffer缓存的数据需要通过setVertexBuffer(_:offset:index:)方法传递到顶点着