【洛谷】P1576 最小花费(最短路--->最长路(通过改边权变定义))

这篇具有很好参考价值的文章主要介绍了【洛谷】P1576 最小花费(最短路--->最长路(通过改边权变定义))。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

分析+变动+ACcode

明确定位最短路,其实就是模板加上稍微改动。

变动位置:

1:把权变成汇率(<=1.0),即经过了这条边,前就要乘以这这边权,即乘以汇率,拿肯定汇率越高最后到终点的钱多(一个道理终点钱指定,拿汇率越高,最开始的钱就可以拿的越少)。我们需要在松弛操作时找尽可能长的边,同时把运算符“<”重载成“>”,保证找到的路径最长.

那就把最短路--->求最长路

dis[a]=1.0;//代表汇率
e[++cnt].dis=1.0-d/100.0;//变成汇率

(当然这可以直接是dis=d/1.00),那就还是求最短路,就到终点权值相乘的最小值(这题独特在我们之前的权值都是加的,这题是乘的)(if(dis[j]<dis[t]*e[i].dis))

2:dis[t]*e[i].dis是乘不是加

if(dis[j]<dis[t]*e[i].dis) { //注意这里是发现更大的dis时更新!!!
				dis[j]=dis[t]*e[i].dis;
				q.push((node){dis[j],j});
			}

3:那么,刚开始初始化就要为0

void init() { //初始化
	for(int i=1; i<=n; i++)
		dis[i]=0;   //注意不要设置成正无穷!!!
}

ACcode: 

#include <bits/stdc++.h>
using namespace std;
struct edge {
	int to,nxt;
	double dis;
} e[200010];
struct node {//重载 
	double dis;
	int pos;
	bool operator <(const node &x)const {
		return x.dis>dis;  //注意重载成大于!!!,就是优先队列用less
	}
};

double head[4010],dis[4010];
bool vis[200010];
int n,m,s,cnt,a,b;

void addedge(int u,int v,int d) { //建边
	e[++cnt].dis=1.0-d/100.0;//变成汇率 
	e[cnt].to=v;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}
priority_queue<node>q;
void init() { //初始化
	for(int i=1; i<=n; i++)
		dis[i]=0;   //注意不要设置成正无穷!!!
}
void dijkstra() {  //优先队列优化的dijkstra
	dis[a]=1.0;//代表汇率
	q.push((node) {1.0,a});
	while(!q.empty()) {
		int t =q.top().pos;
		q.pop();
		if(vis[t])continue;
		vis[t]=1;
		for(int i=head[t]; i; i=e[i].nxt) {
			int j=e[i].to;
			if(dis[j]<dis[t]*e[i].dis) { //注意这里是发现更大的dis时更新!!!
				dis[j]=dis[t]*e[i].dis;
				q.push((node){dis[j],j});
			}
		}
	}
}
int main() {
	scanf("%d%d",&n,&m);
	init();
	for(int i=1; i<=m; i++) {
		int u,v,d;
		scanf("%d%d%d",&u,&v,&d);
		addedge(u,v,d);
		addedge(v,u,d);  //注意建边2次!!!
	}
	scanf("%d%d",&a,&b);
	dijkstra();
	printf("%.8lf",100.0/dis[b]);  //注意是100/dis[b]
	return 0;
}

over~文章来源地址https://www.toymoban.com/news/detail-553001.html

到了这里,关于【洛谷】P1576 最小花费(最短路--->最长路(通过改边权变定义))的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 动态规划之使用最小花费爬楼梯

    题目链接选自力扣 : 使用最小花费爬楼梯 先根据示例 1 来理解一下题目的意思. 可以看到, 此时一共有两个起始位置 0 ,1. 并且这三个位置都对应了一定的费用 10, 15 当我们选择从某个地方开始想要向上走就得支付当前位置的费用才可以向上一格或者两格. 当前这个示例就是从

    2024年02月10日
    浏览(63)
  • LeetCode使用最小花费爬楼梯(动态规划)

    链接: 使用最小花费爬楼梯 题目描述 算法流程(方法一) 编程代码 优化代码 算法流程(方法二) 编程代码 代码优化

    2024年02月15日
    浏览(31)
  • 【算法】动态规划1,最小花费爬楼梯,解码方法

    动态规划 , 英文名称 Dynamic Programming , 简称 DP , 不是具体的某种算法 , 是一种算法思想 ; 动态规划 , 没有具体的步骤 , 只有一个核心思想 ; 动态规划 的 核心思想 是 由大化小 , 大规模问题 使用 小规模问题 计算结果 解决 , 类似于 分治算法 ; 例题1 通过分析最近的一步来划分问

    2024年02月21日
    浏览(39)
  • 动态规划之使用最小花费爬楼梯【LeetCode】

    LCR 088. 使用最小花费爬楼梯 状态表示 ( 这是最重要的 ):dp[i]表示以第i级台阶为楼层顶部,到达第i层台阶的最低花费。 状态转移方程 ( 最难的 ): dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]); 初始化 :根据题意,我们需要知道到达第1层和第2层台阶的最低花费,第1层和第2层

    2024年03月16日
    浏览(41)
  • 【leetcode刷题】66.使用最小花费爬楼梯——Java版

    ⭐欢迎订阅《leetcode》专栏,每日一题,每天进步⭐ 我觉得这个题的描述应该改改:每个阶梯都有一定数量坨屎,一次只能跨一个或者两个阶梯,走到一个阶梯就要吃光上面的屎,问怎么走才能吃最少的屎?开局你选前两个阶梯的其中一个作为开头点,并吃光该阶梯的屎。

    2023年04月08日
    浏览(79)
  • 【C++】洛谷B3637 最长上升子序列

    这是一个简单的动规板子题。 给出一个由 n ( n ≤ 5000 ) n(nle 5000) n ( n ≤ 5000 ) 个不超过 1 0 6 10^6 1 0 6 的正整数组成的序列。请输出这个序列的 最长上升子序列 的长度。 最长上升子序列是指,从原序列中 按顺序 取出一些数字排在一起,这些数字是 逐渐增大 的。 第一行,一

    2024年02月19日
    浏览(31)
  • 洛谷题单 Part 8.2 最短路问题

    最短路算法一般在算法竞赛中有四种比较常见, F l o y d Floyd Fl oy d 算法, B e l l m a n − F o r d Bellman-Ford B e ll man − F or d 算法, D i j k s t r a Dijkstra D ijk s t r a 算法, S P F A SPFA SPF A 算法。 F l o y d Floyd Fl oy d 算法和 B e l l m a n − F o r d Bellman-Ford B e ll man − F or d 算法的时间复杂

    2024年02月09日
    浏览(50)
  • 动态规划解决泰波那契数列,爬楼梯最小花费问题

    做题之前我们需要先搞清楚解决动态规划的几个步骤 1 状态表示,准备一个dp表 2 状态转移方程  3 初始化 4 填表 5 返回值 步骤1 状态表示,准备dp表 dp[0] dp[1] dp[2] dp[3] dp[4] = dp[0]+dp[1]+dp[3] 步骤2 状态转移方程表示 dp[i] = dp[i-1]+dp[i-2]+dp[i-3] 步骤3 4 5 都是对代码的细节处理,代码

    2024年02月03日
    浏览(31)
  • LeetCode:509. 斐波那契数 && 70. 爬楼梯 && 746. 使用最小花费爬楼梯

    斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是: F(0) = 0,F(1) = 1 F(n) = F(n - 1) + F(n - 2),其中 n 1 给定 n ,请计算 F(n) 。 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬

    2024年02月05日
    浏览(46)
  • DAY42:动态规划(二)斐波那契数列+爬楼梯+最小花费爬楼梯

    斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是: 给定 n ,请计算 F(n) 。 示例 1: 示例 2: 示例 3: 提示: 0 = n = 30 思路:动规五步 确定dp数组和数组下标含义 DP题目都需要定义一维

    2024年02月13日
    浏览(56)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包