请选择 进入手机版 | 继续访问电脑版
MSIPO技术圈 首页 IT技术 查看内容

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

2023-07-13

分析+变动+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~

相关阅读

热门文章

    手机版|MSIPO技术圈 皖ICP备19022944号-2

    Copyright © 2024, msipo.com

    返回顶部