首页 > 其他分享 >P9504 『MGOI』Simple Round I | C. 魔法禁林

P9504 『MGOI』Simple Round I | C. 魔法禁林

时间:2023-08-07 21:34:03浏览次数:41  
标签:MGOI dist Simple int second 禁林 100 include id

赛时第一眼看,是个无向图,求一个点到另外一个点的最小值,诶,这不裸的最短路嘛,然后兴高采烈地倒着跑了个 dijkstra,喜提 \(30\) 分。仔细一看,\(w \le 100\),发现当 \(k > 100\) 时,生命就是永恒的,于是加了个剪枝,就过啦。

具体地,正常的最短路量有一个,本题有两个。于是我们定义 \(dist_{i,j}\) 表示当前魔力值为 \(i\) 走到 \(j\) 的最小生命值。每倒着走一条边,\(k\) 就多了 \(1\)。当 \(k > 100\) 时,往后无论怎么走,生命值都不会减少,\(k\) 就不用加了,直接跳过这个状态即可。其他和裸最短路没啥区别。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

#define PII pair<int, pair<int, int> >
#define x first
#define y second

const int N = 20010, M = 80010;

inline void in(int &x)
{
	x = 0; bool f = 0; char c = getchar();
	while(c < '0' || c > '9')
	{
		if(c == '-') f = 1;
		c = getchar();
	}
	while(c >= '0' && c <= '9')
	{
		x = (x << 3) + (x << 1) + (c & 15);
		c = getchar();
	}
	x = f ? -x : x;
}

inline void out(int x)
{
	if(x < 0) putchar('-'), x = -x;
	if(x / 10) out(x / 10);
	putchar((x % 10) | 48);
}

int n, m, s, t;
int h[N], e[M], ne[M], w[M], idx;
int dist[210][N], res[N];
bool st[210][N];
priority_queue<PII, vector<PII>, greater<PII> > q;

inline void add(int a, int b, int c)
{
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
	return;
}

void dijkstra()
{
	memset(dist, 0x3f, sizeof dist);
	dist[0][s] =0;
	q.push({0, {0, s}});
	
	while (!q.empty())
	{
		PII p = q.top();
		q.pop();
		
		int id = p.second.second, k = p.second.first;
		//对于一个  PII,first 表示最小生命值,second.first 表示当前魔法值,second.second 表示当前结点编号 
		if(st[k][id]) continue;
		st[k][id] = 1;
		
		if(k > 100) continue; //剪枝 
		
		for (int i = h[id]; ~i; i = ne[i])
		{
			int j = e[i];
			if(dist[k + 1][j] > dist[k][id] + w[i] / (k + 1))
			{
				dist[k + 1][j] = dist[k][id] + w[i] / (k + 1);
				q.push({dist[k + 1][j], {k + 1, j}});
			} //更新状态 
		}
	}
	return;
}

int main()
{
	memset(h, -1, sizeof h);
	
	in(n); in(m); in(t); in(s); //倒着做 
	while (m -- )
	{
		int x, y, z;
		in(x); in(y); in(z);
		add(x, y, z); add(y, x, z);
	}
	
	dijkstra();
	
	int ans = 0x3f3f3f3f;
	for(int i = 0; i <= 101; i ++ ) ans = min(ans, dist[i][t]);
	printf("%d\n", ans);
	
	return 0;
}

标签:MGOI,dist,Simple,int,second,禁林,100,include,id
From: https://www.cnblogs.com/3042651coding/p/17612765.html

相关文章

  • 【LGR-148-Div.3】洛谷基础赛 #1 & MGOI Round I
    【LGR-148-Div.3】洛谷基础赛#1&MGOIRoundIT1luoguP9502『MGOI』SimpleRoundI|A.魔法数字\(100pts\)水题,场切了。#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#definesortstable_sort#defineendl'\n'intmain(){ ......
  • 『MGOI』Simple Round I | B. 魔法照相馆 题解
    题目传送门一道模拟题。并不复杂的模拟题,也不需要用到贪心。我们可以创建一个数组来记录每个幕布是否被拉上,统计答案的时候,就看看这块幕布前面有多少个没拉上的,最后如果这块幕布拉上了,就重新放下来就行了。#include<bits/stdc++.h>#definelllonglong#defineINF1e9usi......
  • 【题解】Luogu[P9504] 『MGOI』Simple Round I C. 魔法禁林
    Link这题我们发现如果直接去枚举生命和法力值显然是不行的,又看到说最小的生命值,不禁想到最短路,但是怎么跑?我们令经过一条边之前魔力值为\(k\),那么该边的边权为\(\lfloor\dfrac{w}{k}\rfloor\),于是我们讲题目转化为了边权为\(\lfloor\dfrac{w}{k}\rfloor\)时\(s\)到\(t\)......
  • 【LGR-148-Div.3】洛谷基础赛 #1 & MGOI Round I
    【LGR-148-Div.3】洛谷基础赛#1&MGOIRoundI据说是普及组难度?T1P9502『MGOI』SimpleRoundI|A.魔法数字\(100pts\)题目描述初级魔法士小M的魔法数字是\(2\)。给定一个正整数\(n\),小M需要找到最大的偶数\(m\),使得\(2^m<n\)。又双叒叕是个水题,然后被又双......
  • 【LGR-148-Div.3】洛谷基础赛 #1 & MGOI Round I
    T1简单题,题面十分清晰,就是给我们\(n\),要求使\(2^m<n\)成立的最小偶数\(m\)。(要注意\(log_2N=m,m|2\)的情况)#include<bits/stdc++.h>#definelllonglong#definereregisterusingnamespacestd;constintN=800,INF=0x3f3f3f3f;lln;intmain(){ cin>>n; llk=log......
  • 《安富莱嵌入式周报》第319期:声音编程器,开源激光雕刻机,自制600W海尔贝克无刷电机,车用
    周报汇总地址:http://www.armbbs.cn/forum.php?mod=forumdisplay&fid=12&filter=typeid&typeid=104 更新视频教程:更新第7期ThreadX视频教程:如何实现RTOS高效的任务管理,抢占式调度,时间片调度和零中断延迟(2023-07-31)https://www.armbbs.cn/forum.php?mod=viewthread&tid......
  • 【高并发】SimpleDateFormat类到底为啥不是线程安全的?(附六种解决方案,建议收藏)
    大家好,我是冰河~~首先问下大家:你使用的SimpleDateFormat类还安全吗?为什么说SimpleDateFormat类不是线程安全的?带着问题从本文中寻求答案。提起SimpleDateFormat类,想必做过Java开发的童鞋都不会感到陌生。没错,它就是Java中提供的日期时间的转化类。这里,为什么说SimpleDateFormat类有......
  • simpleui插件相关
    目录关于simpleui准备阶段实际操作superserverpip和apps测试语言、logo后台名关闭广告自定义APP名修改中文优化操作设置主题自定义菜单自定义首页应用到coalpress项目出现的问题问题一问题二应用实操执行创建超级用户启动服务进入后台django-import-export安装到app关于simpleu......
  • SimpleDateFormat线程安全问题探究
    目录一.问题现象二.原因排查三.原因分析四.解决方案一.问题现象运营部门反馈使用小程序配置的拉新现金红包活动二维码,在扫码后跳转至404页面。二.原因排查1、首先,检查扫码后的跳转链接地址不是对应二维码的实际URL,根据代码逻辑推测,可能是accessToken在微信端已失效导致,检查数......
  • rest-apiV2.0.0升级为simplest-api开源框架生态之simplest-jpa发布
    什么是simplestsimplest追求存粹简单和极致。旨在为项目快速开发提供一系列的基础能力,方便用户根据项目需求快速进行功能拓展不在去关心一些繁琐。重复工作,而是把重点聚焦到业务。前言程序10年。作为一个多年程序。深知每个项目和程序,都有很多重复性工作要做。入行近10......