首页 > 其他分享 >有边数限制的最短路

有边数限制的最短路

时间:2024-01-27 09:03:51浏览次数:22  
标签:输出 限制 int 短路 条边 边数 号点

第3题     有边数限制的最短路 查看测评数据信息

给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环, 边权可能为负数。请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离,如果无法从 1 号点走到 n 号点,输出 impossible。注意:图中可能 存在负权回路 。1≤n,k≤500 ,1≤m≤10000,任意边长的绝对值不超过 10000。

输入格式

 

第一行包含三个整数 n,m,k。

接下来 m 行,每行包含三个整数 x,y,z,表示存在一条从点 x 到点 y 的有向边,边长为 z。

 

输出格式

 

输出一个整数,表示从 1 号点到 n 号点的最多经过 k 条边的最短距离。如果不存在满足条件的路径,则输出 impossible。

 

输入/输出例子1

输入:

3 3 1

1 2 1

2 3 1

1 3 3

 

输出:

3

 

样例解释

 

 

 

这题其实并不算Bellman-ford的题,应该是动态规划

 

 

 

 

#include <bits/stdc++.h>
using namespace std;

const int N=1e4+5, M=505;
struct edge
{
	int u, v, w;
}a[N];
int n, m, k, x, y, z;
int dis[N][M], ans=0;
int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i=1; i<=m; i++)
    {
    	scanf("%d%d%d", &x, &y, &z);
    	a[i]={x, y, z};
	}
	
	memset(dis, 63, sizeof dis);
    ans=dis[0][0];
	dis[1][0]=0;
	
	for (int i=1; i<=k; i++) //松弛k轮并不可行,并不一定松弛了k条边,所以这里的i表示边数
	{
		for (int j=1; j<=m; j++)
		{
			int u=a[j].u, v=a[j].v, w=a[j].w;
			if (dis[u][i-1]+w<dis[v][i]) //u点是起点,到起点需要减1条边,然后加上u点到v点的距离,这样就是dis[v][i]了
				dis[v][i]=dis[u][i-1]+w;
		} 
	}
	
	for (int i=0; i<=k; i++) ans=min(ans, dis[n][i]); 
	
    
    if (ans<dis[0][0]) printf("%d", ans);
    else printf("impossible");
    return 0;
}

 

标签:输出,限制,int,短路,条边,边数,号点
From: https://www.cnblogs.com/didiao233/p/17991058

相关文章

  • 容器中的JVM资源该如何被安全的限制?
    前言Java与Docker的结合,虽然更好的解决了application的封装问题。但也存在着不兼容,比如Java并不能自动的发现Docker设置的内存限制,CPU限制。这将导致JVM不能稳定服务业务!容器会杀死你JVM进程,而健康检查又将拉起你的JVM进程,进而导致你监控你的Pod一天重启次数甚至能达到几百次。......
  • 什么是真正的ChatGPT——ChatGPT的工作原理、优点和限制分析
     什么是真正的ChatGPT——ChatGPT的工作原理、优点和限制分析前言 ChatGPT是一种基于人工智能技术的智能聊天机器人,由OpenAI提供支持。它可以使用自然语言与用户进行交互,并回答各种问题。ChatGPT采用深度学习技术和大量数据来学习语言模式和上下文,并尝试在回答问题时提供......
  • 警惕!DLS Markets有疑似跑路的先兆?限制客户账户访问且拒绝出金引众怒!
    懂哥前几天听闻DLSMarkets有疑似跑路的先兆?DLSMarkets大致2个月前因为客诉剧增陷入黑平台风波,其原因存在大面积限制客户账户访问且拒绝出金,但DLSMarkets是以专有的新技术平台为交易特点,赢得不少投资人好感。期间却又爆出似乎存在经营困难,有跑路风险?真的是这样吗?      ......
  • dijkstra算法(单源最短路径)
    单源最短路径是求解给定一个起点到其他所有的点的最短距离。适用的范围:有向图、边的权值没有负数洛谷测试链接代码实现#define_CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<stdlib.h>#include<string.h>#include<math.h>#include<time.h>#include<stdboo......
  • 图的最短路-Dijkstra 详解
    Dijkstra  概念注意一下,Dijkstra不适用于有负边权的图   就是刚开始一些点(集合B),把排序的结果放入集合A,先确定起点0,然后找集合B里面的最小值,这样才可以确定你修改的这个点的最短路在目前是最优解(后期可能改动),因为集合A的都是确定好了的最短路,所以集合A的数不做修......
  • 自从知道止损限制,fpmarkets发现交易变得容易多
    当交易者知道什么是止损限制,fpmarkets交易就变得容易多了。毕竟买入止损点可以用于回跌,也可以突破关键水平。交易者只需在低于止损价的水平设置限价单。买入/卖出止损遵循相同的概念。但随着卖出,目前的市场位置在关键水平之上,预期向下击穿。用图举例,交易者预期的熊市趋势。但是因为......
  • Microsoft 365 解决方案:Security Group与Conditional Access强强联手限制不同用户的MF
    51CTO博客链接:https://blog.51cto.com/u_13637423多重身份验证(MFA)为登录流程增加了一层保护。访问帐户或应用时,用户需要提供额外的身份验证,例如扫描指纹或输入手机收到的验证码,确保你用于高风险帐户的凭据可以防止网络钓鱼和渠道入侵。MicrosoftEntra中的MFA会要求使用以下......
  • [转帖]能使 Oracle 索引失效的六大限制条件
    Oracle索引的目标是避免全表扫描,提高查询效率,但有些时候却适得其反。例如一张表中有上百万条数据,对某个字段加了索引,但是查询时性能并没有什么提高,这可能是oracle索引失效造成的。oracle索引有一些限制条件,如果你违反了这些索引限制条件,那么即使你已经加了索引,oracle......
  • 分布图最短路径算法比较
    用户维护好仓区的点和线,生成分布图时,用户任意选取两个点,后端求出当前最短路径。假设图G(m,n),m个顶点,n条边算法对比:floyd算法时间复杂度o(m3)缺点:时间复杂度过高dijkstra算法时间复杂度o(m2),使用优先队列可以降到o(m*logm)邻接矩阵存储:适合稠密图邻接表存储:适合稀疏图缺点:不适......
  • 主流云平台上虚机的网络带宽限制
    比方说,你有一块100Gbps的物理网卡,那么这个100Gbps的指标意味着这块网卡最多可以每秒100Gbit/sec的速率传输数据,这个限制意味着进入和传出的数据加起来不能超过100Gbit/sec。在AWS平台上,其EC2的Instance(VM)的网络带宽的限制与上面描述的传统概念相一致,都是对进入和传出的数据的共......