您现在的位置是:首页 > 正文

SPFA——路障Roadblocks

2024-01-30 23:29:30阅读 2

题目来源

洛谷P2865 [USACO06NOV]路障Roadblocks

https://www.luogu.org/problemnew/show/2865

POJ3255 Roadblocks

http://poj.org/problem?id=3255


思路

将每条无向边拆成两条有向边 建图

分别以1、n为原点SPFA求最短路 分别记为dis1[i]、dis2[i]

枚举每一条有向边i(起点为u 终点为v 长度为w)

经过该有向边i的最短路长即为 dis1[u]+w+dis2[v]

求这些“最短路长”中比“真·最短路”长的最短长度


代码(C++)

#include <cstdio>
#include <queue>
#include <bitset>
#define N 5010
#define M 200010
using namespace std;
bitset<N> in;	queue<int> q;
int n,m,u,v,w,cnt=0,pos;
int he[N],fr[M],en[M],ne[M],len[M];
long long ll,dis1[N],dis2[N],minl,ans;
inline void add();
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)
		scanf("%d%d%d",&u,&v,&w),add();
	for(int i=1;i<=n;++i)
		dis1[i]=dis2[i]=9223372036854775807;
	ans=9223372036854775807;
	dis1[1]=0; in[1]=1;	q.push(1);
	while(!q.empty())
	{
		pos=q.front(); q.pop(); in[pos]=0;
		for(int k=he[pos];k!=0;k=ne[k])
			if(dis1[pos]+len[k]<dis1[en[k]])
			{
				dis1[en[k]]=dis1[pos]+len[k];
				if(in[en[k]]==0)
					q.push(en[k]),in[en[k]]=1;
			}
	}
	dis2[n]=0; in[n]=1;	q.push(n);
	while(!q.empty())
	{
		pos=q.front(); q.pop(); in[pos]=0;
		for(int k=he[pos];k!=0;k=ne[k])
			if(dis2[pos]+len[k]<dis2[en[k]])
			{
				dis2[en[k]]=dis2[pos]+len[k];
				if(in[en[k]]==0)
					q.push(en[k]),in[en[k]]=1;
			}
	}
	minl=dis1[n];
	for(int i=1;i<=cnt;++i)
	{
		ll=dis1[fr[i]]+dis2[en[i]]+len[i];
		if(ll>minl&&ll<ans)
			ans=ll;
	}
	printf("%lld",ans);
	return 0;
}
inline void add()
{
	en[++cnt]=v;	len[cnt]=w;
	ne[cnt]=he[u];	he[u]=cnt;  fr[cnt]=u;
	en[++cnt]=u;	len[cnt]=w;
	ne[cnt]=he[v];	he[v]=cnt;  fr[cnt]=v;
}


网站文章

  • element-ui upload组件完美适配oss 解决方案

    element-ui upload组件完美适配oss 解决方案

    oss 存储方案1 oss 基础配置1 .1创建bucket1.2 创建子账户创建用户并授予编程访问权限:创建用户成功后的样式:1.3 授权完成oss所有的权限2 oss 官方文档地址2.1 官方帮助...

    2024-01-30 23:28:59
  • 解决a标签点击失效问题

    解决a标签点击失效问题

    问题描述:当鼠标移动到退出时,不发生变化且点击没有效果,在我更改样式后。 原因:a标签被其他层级覆盖了 设置a标签样式 a{ z-index: 9999; position: relative; display: inline-block; } 成功

    2024-01-30 23:28:52
  • android快速开发ui框架!整理几个重要的Android知识,吐血整理

    很多程序员都有这样的觉悟;找工作学历是敲门砖,没有211,985起步的学历,想进一家大公司不太可能。 举个例子好了; 如果你是大厂面试官,参与面试的有10个刚刚毕业没有工作经验的普通学校应届生,还有1...

    2024-01-30 23:28:44
  • windows10安装tensorflow-gpu1.13.1与tensorflow-gpu2.0.0教程

    windows10安装tensorflow-gpu1.13.1与tensorflow-gpu2.0.0教程

    我安装tensorflow-gpu时总是出现问题,特别是tensorflow-gpu、cuda、cudnn的版本不对应会出现很多奇怪的错误提示,希望这篇记录对我以后也有所帮助。

    2024-01-30 23:28:15
  • 网页动态线条特效

    网页动态线条特效

    首先,附上作者的链接:https://github.com/hustcc/canvas-nest.js 然后:最好使用方法二,方法二可以在本地的文件中修改一些参数,使线条达到我们想要达到的效果,而且可以把js放到js的文件中,不占用html或者jsp页面中的内容等,一般来说,js单独另存,在页面中引用js存在的位置即可。 &amp;...

    2024-01-30 23:28:07
  • java system.out输出到哪里_将System.out.println() 输出重定向到Java中的文件 - Break易站...

    System.out.println()主要用于将消息打印到控制台。然而,我们中很少有人真正意识到其工作机制。System是java.lang包中定义的类。out是PrintStream的一个实例 ,它是System类的公共和静态成员。由于PrintStream类的所有实例都有一个公共方法println(),因此我们也可以在out上调用它。我们可以假设System.out代表标准的输出流。...

    2024-01-30 23:27:31
  • postgres docker中查询数据库

    postgres docker中查询数据库

    文章目录1 问题2 操作流程 1 问题 项目的postgres是通过docker提供服务 现在需要进入数据库中查询数据 2 操作流程 进入docker docker exec -it 容器id /bin/bash 进入数据库 psql -U 用户名 数据库名 现在可执行sql语句 ...

    2024-01-30 23:27:23
  • 文心大模型4.0正式发布!来看看这届百度世界有啥亮点

    文心大模型4.0正式发布!来看看这届百度世界有啥亮点

    今天,2023百度世界大会开幕了,大家都关注了吗?本次大会有很多亮点,我先摘一些和大家分享。- 李彦宏现场做「手把手教你做AI原生应用」的分享,百度很多产品通过大模型进行了重构。- 文心大模型4.0重磅发布,综合水平与GPT4相比已经毫不逊色!- 全新百度网盘、百度搜索、百度地图、百度新文库等齐亮相。- 国内首个生成式商业智能产品,百度GBI 发布。

    2024-01-30 23:27:16
  • 路由基础

    路由器——用于网络互连的计算机设备。作用:实现网络互连,数据转发路由(寻址):路由表建立,刷新交换:在网桥之间转发分组数据隔离广播,指定访问规则异种网络互连子网间的速率匹配路由表:当路由器检查到包的目的IP地址时,他就可以根据路由表的内容决定包应该转发到哪个下一跳地址上去。同网段内通信: ...

    2024-01-30 23:27:09
  • softmax损失函数

    最终,我们的目标就是通过不断地迭代训练数据,让模型的 softmax 计算得到的概率值尽可能地接近真实标记,而并不是最大化概率值。那么我们可以设计一个交叉熵损失函数来量化模型的预测值和真实值之间的误差...

    2024-01-30 23:26:38