首页 > 其他分享 >Codeforces Round 918 G. Bicycles (二维最短路)

Codeforces Round 918 G. Bicycles (二维最短路)

时间:2024-07-01 11:52:39浏览次数:22  
标签:newsp const dij int Bicycles Codeforces 因子 918 sped

G. Bicycles

image
image
image
题意:在一个无向图里你要从1点到达n点,每条路的路径长度是该路的权值乘于你当前的慢度因子。而在每个点上我们都有一个慢度因子可以进行更换,问你到达n点所需要的最短时间。

思路:我们很容易想到每次遇到更小的慢度因子我们就要更换,但因为存在你先去绕远路拿更小的慢度因子然后再去终点答案更优于直接找一条最短路的情况。所以我们可以用d[点][因子]这种二维形式来表示每个点上我们用当前这个因子跑的距离。然后跑一遍dij算法,每次拓展当前因子的最优答案,最后从d[n][i]遍历到1000就能找到最优解。

注意下方代码折叠!~~~~

点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 1e18;
const int N = 1e3+100;
int n,m,w[N],d[N][N];
bool vis[N][N];
struct node{//建图用 
	int z,leh;
};
vector<node> h[N];
void add(int u,int v,int z)
{
	h[u].push_back({v,z});
	h[v].push_back({u,z});
}
struct edge{//根堆结构体 
	int num,len;
	bool operator > (const edge &t) const
	{
		return len>t.len;
	} 
	int v;
};
void init()//初始化 
{
	for(int i=0;i<=n;i++){
		for(int j=0;j<=1000;j++){
			vis[i][j]=0,d[i][j]=inf;
		}
	}
	for(int i=0;i<=n;i++) h[i].clear();
}
void dij(int x)
{
	priority_queue<edge,vector<edge>,greater<edge> > q;
	q.push({x,0,w[x]});
	d[x][w[x]]=0;
	while(q.size())
	{
		auto t=q.top();
		q.pop();
		int u=t.num,sped=t.v,ds=t.len;
		if(vis[u][sped]==1) continue;
		vis[u][sped]=1;
		for(auto p:h[u])
		{
			int v=p.z,dd=p.leh;
			int newsp=min(sped,w[v]);//替换更小的因子 
			if(d[v][newsp]>d[u][sped]+dd*sped)//拓展边 
			{
				d[v][newsp]=d[u][sped]+dd*sped;
				q.push({v,d[v][newsp],newsp});
			}
		}
	}
}
void solve()
{
	int res=1e18;
	cin>>n>>m;
	init();
	for(int i=1;i<=m;i++)
	{
		int u,v,z;
		cin>>u>>v>>z;
		add(u,v,z);
	}
	for(int i=1;i<=n;i++) cin>>w[i];
	dij(1);
	for(int i=0;i<=1000;i++)//因子最大为1000,直接遍历寻找答案 
	{
		res=min(res,d[n][i]);
	}
	cout<<res<<endl;
}
signed main()
{
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

注意:小根堆因为是开的结构体所以要重载,把最小距离放在堆顶就是堆优化dij的贪心思路,但就算把最大距离放在堆顶也能AC就是会多跑点时间。

结语:此题难度不大,应该算是dij入门类的题目,但是第一次遇到应该会想一会。主要就是想到怎么用二维的形式去表示dij从原本一个距离变成距离和速度两个因素。

El Psy Congroo" - Okabe Rintaro!

标签:newsp,const,dij,int,Bicycles,Codeforces,因子,918,sped
From: https://www.cnblogs.com/onlypasserby/p/18277770

相关文章

  • Codeforces Round 894 (Div. 3) A-E cd 894 div3
    A.GiftCarpet每道题都是伸缩代码框有ac代码请不要漏掉--------------------------题解-----------------------------按先行便然后列再变循环设置jud每满足一个条件就让jud++只有jud==相应值的时候才让其++点击查看代码#include<bits/stdc++.h>usingnamespacestd;ch......
  • Codeforces Round 954 (Div. 3)
    A.XAxis题意:给3个x轴上的点xi,我们要放置一个点到x轴上,到这3个点的距离最短。(1<=xi<=10)思路:直接暴力破解即可inta,b,c;inlineintcal(intx){ returnabs(x-a)+abs(x-b)+abs(x-c);}voidsolve(){ cin>>a>>b>>c; intans=(int)1e9; for......
  • 创新实训 (九)CodeForces 数据和微调数据处理
    Codeforces数据获取Codeforces的题目中存在一些数学公式,所以处理的时候需要比较小心的对其进行处理。首先是题面数据,在CF当中标识一道题目的方式是problemSet与problemId。其中problemSet是一个数字,而problemId是一个字母。另外需要注意的是CF题面中存在许多数学......
  • 板刷codeforces构造题
    前言听说多写构造题可以提升思维能力...C.TurtleandanIncompleteSequence题目大意给定一个数组a,只有正整数和-1,-1可以改为正整数,问数组能否满足$\lfloora[i]/2\rfloor=a[i+1]或\lfloora[i+1]/2\rfloor=a[i]$,能则输出方案解题思路可以发现,相邻2个数在完全......
  • Codeforces Round 952 (Div. 4)
    知识点模块1.一个正方体x,y,z里面可以放多少个边长为a,b,c的长方体ans=(x-a+1)*(y-b+1)*(z-c+1)题解模块A.CreatingWords交换两个字母的首字母即可swap实现即可点击查看代码#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongtypedefpair<int,int>......
  • Codeforces Round 953 (Div. 2) A - F
    A编号为\(n\)的一定选,第二叠书在\(1\simn-1\)选最大的。voidsolve(){ cin>>n; for(inti=1;i<=n;++i){ cin>>a[i]; } intans=a[n]; intx=0; for(inti=1;i<n;++i){ x=max(x,a[i]); } cout<<ans+x<&......
  • Codeforces Round 953 Div.2 F 题解
    连通块计数的一种常见思路是钦定代表元,但发现这题的连边方式并不好指定一个代表元,那么只能尝试优化建图。我们尝试观察一下连边的情况,通过手玩样例获得一些几何直观的感受:345534453这个样例也许比较小,不过你真的把边画出来就会发现:连边形如\(2n-1\)条完整的斜线,中间......
  • Codeforces Round 953 (Div. 2)(A~D题解)
    这次比赛是我最顺利的一次比赛,也是成功在中途打进前1500,写完第三道题的时候也是保持在1600左右,但是后面就啥都不会了,还吃了点罚时,虽说如此也算是看到进步了,D题学长说很简单,但是我当时分析错了,出了一点小问题,不然最后也能定格在2000左右,下次加油。A.AliceandBooks 题意:......
  • Codeforces Round 952 (Div. 4) G. D-Function(思维)
    Problem-G-Codeforces思维题,推出公式用等比数列求和做一下。1#defineIOstd::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)2#definebug2(x,y)cout<<#x<<"is"<<x<<""<<#y<<"is"<<y<<end......
  • CodeForces 1935A
    题目链接:EntertainmentinMAC思路代码#include<bits/stdc++.h>usingnamespacestd;#definelllonglongconstintN=1e5+10;voidsolve(){lln;strings;cin>>n>>s;intl=0,len=s.size();while(s[l]==s[......