拆点____ 行车路线

2023-11-21 00:20
文章标签 路线 行车 ____ 拆点

本文主要是介绍拆点____ 行车路线,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

3255. 行车路线

小明和小芳出去乡村玩,小明负责开车,小芳来导航。

小芳将可能的道路分为大道和小道。

大道比较好走,每走 1 公里小明会增加 1 的疲劳度。

小道不好走,如果连续走小道,小明的疲劳值会快速增加,连续走 s 公里小明会增加 s^2 的疲劳度。

例如:有 5 个路口,1 号路口到 2 号路口为小道,2 号路口到 3 号路口为小道,3 号路口到 4 号路口为大道,4 号路口到 5 号路口为小道,相邻路口之间的距离都是 2 公里。

如果小明从 1 号路口到 5 号路口,则总疲劳值为 (2+2)^2+2+2^2=16+2+4=22。

现在小芳拿到了地图,请帮助她规划一个开车的路线,使得按这个路线开车小明的疲劳度最小。

输入格式

输入的第一行包含两个整数 n,m,分别表示路口的数量和道路的数量。路口由 1 至 n 编号,小明需要开车从 1 号路口到 n 号路口。

接下来 m 行描述道路,每行包含四个整数 t,a,b,c,表示一条类型为 t,连接 a 与 b 两个路口,长度为 c 公里的双向道路。其中 t 为 0 表示大道,t 为 1 表示小道。

保证 1 号路口和 n 号路口是连通的。

输出格式

输出一个整数,表示最优路线下小明的疲劳度。

数据范围

对于 30% 的评测用例,1≤n≤8,1≤m≤10;
对于另外 20% 的评测用例,不存在小道;
对于另外 20% 的评测用例,所有的小道不相交;
对于所有评测用例,1≤n≤500,1≤m≤10^5,1≤a,b≤n,t 是 0 或 1,c≤10^5。
保证答案不超过 10^6

输入样例:
6 7
1 1 2 3
1 2 3 2
0 1 3 30
0 3 4 20
0 4 5 30
1 3 5 6
1 5 6 1
输出样例:
76
样例解释

从 1 走小道到 2,再走小道到 3,疲劳度为 5^2=25;然后从 3 走大道经过 4 到达 5,疲劳度为 20+30=50;最后从 5 走小道到 6,疲劳度为 1。

总共为 76。

因为保证答案不超过10^6, 所以连续小路长度超过1000
因为点的数据范围为500,所以可以拆点,第二维表示当前连续小路长度 

#include <bits/stdc++.h>using namespace std;const int N = 510, M = 200010, INF = 1e6;int n, m;
int h[N], e[M], f[M], w[M], ne[M], idx;  //f表示道路类型
int dist[N][1010];
bool st[N][1010];struct Node
{int x, y, v;  //x当前点,y当前连续小路长度,v为dist[x][y]bool operator< (const Node& t) const{return v > t.v;  //小根堆(从小到大)}
};void add(int t, int a, int b, int c)
{e[idx] = b, f[idx] = t, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}void dijkstra()
{memset(dist, 0x3f, sizeof dist);dist[1][0] = 0;priority_queue<Node> heap;heap.push({1, 0, 0});while (heap.size()){Node t = heap.top();heap.pop();if (st[t.x][t.y]) continue;  //dijkstra()所有点只遍历一次st[t.x][t.y] = true;for (int i = h[t.x]; ~i; i = ne[i]){int j = e[i], y = t.y;if (f[i])  //小路{y += w[i];  //小路长度更新if (y <= 1000)  //连续小路长度一定小于1000{if (dist[j][y] > t.v - t.y * t.y + y * y){dist[j][y] = t.v - t.y * t.y + y * y;if (dist[j][y] <= INF)heap.push({j, y, dist[j][y]});}}}else{if (dist[j][0] > t.v + w[i]){dist[j][0] = t.v + w[i];if (dist[j][0] <= INF)heap.push({j, 0, dist[j][0]});}}}}
}int main()
{cin >> n >> m;memset(h, -1, sizeof h);while (m --){int t, a, b, c;scanf("%d%d%d%d", &t, &a, &b, &c);add(t, a, b, c), add(t, b, a, c);}dijkstra();int res = INF;for (int i = 0; i <= 1000; i ++) res = min(res, dist[n][i]);//表示最后一段小路的长度为i的前提下,1到n的最短距离cout << res;return 0;
}

 

这篇关于拆点____ 行车路线的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/398466

相关文章

poj 3422 有流量限制的最小费用流 反用求最大 + 拆点

题意: 给一个n*n(50 * 50) 的数字迷宫,从左上点开始走,走到右下点。 每次只能往右移一格,或者往下移一格。 每个格子,第一次到达时可以获得格子对应的数字作为奖励,再次到达则没有奖励。 问走k次这个迷宫,最大能获得多少奖励。 解析: 拆点,拿样例来说明: 3 2 1 2 3 0 2 1 1 4 2 3*3的数字迷宫,走两次最大能获得多少奖励。 将每个点拆成两个

大模型的学习路线(非常详细)神仙级教程,手把手教会你

如果读者朋友不想深入学习大模型,则了解提示词的使用原则也可以了。要是既不想深入学习,又要做大模型相关的项目,则对于工程同学来说,学习RAG也能把大模型玩转起来(可参考:[大语言模型RAG落地方案]。下面的步骤写给想系统性学习大模型的朋友们。(后续打算写一个大模型学习系列,详细介绍相关知识点,欢迎关注) 先来一张整体结构图,越是下面部分,越是基础: 可以按以下步骤学习: 1. 理解基础概念

C#/.NET/.NET Core推荐学习路线文档文章

前言 专门为C#/.NET/.NET Core推荐学习路线&文档&文章提供的一个Issues,各位小伙伴可以把自己觉得不错的学习路线、文档、文章相关地址分享出来🤞。 https://github.com/YSGStudyHards/DotNetGuide/issues/10 🏷️C#/.NET/.NET Core优质学习资料 📚.NET 入门教程 📚

龙蜥社区首推 AI 原生操作系统路线,三大重磅计划协同生态布局未来

近日,2024 龙蜥操作系统大会(OpenAnolis Conference)在北京圆满召开,此次大会由中国计算机学会开源发展委员会、中关村科学城委员会、海淀区委网信办、中国开源软件推进联盟指导,龙蜥社区主办,阿里云、浪潮信息、Intel、中兴通讯、Arm、中科方德等 24 家理事单位共同承办,主题为“进化·重构·赴未来”。北京市委网信办、海淀区委网信办等领导莅临指导,中国工程院院士、浙江大学信息

2024最全自学黑客技术学习路线,带你少走一点弯路!

谈起黑客,可能各位都会想到:盗号,其实不尽然;黑客是一群喜爱研究技术的群体,在黑客圈中,一般分为三大圈:娱乐圈 技术圈 职业圈。 娱乐圈:主要是初中生和高中生较多,玩网恋,人气,空间,建站收徒玩赚钱,技术高的也是有的,只是很少见。 技术圈:这个圈子里面的黑客是为了能把黑客技术玩到极致的技术狂人,我最佩服的就是这群人,希望以后自己也能成为这样的人。 职业圈:这里面的人群主要就是玩HC为主了

VS2012配置Opengl以及“无法解析的外部符号 __imp____glutInitWithExit@12,该符号在函数 _glutInit_ATEXIT_HACK@8 中被引用”问题

1、配置步骤 (1)首先下载glut相关文件,下载地址: http://download.csdn.net/detail/u013383042/9329101 (2)glut.h:头文件,将其复制到 D:\Program Files (x86)\Microsoft Visual Studio 11.0\VC\include\gl (原本没有gl文件夹,需要手动新建一个gl文件夹) (3)

2024 年 Python 学习路线推荐,附学习书籍,学习视频(建议收藏)

文章目录 一、前言二、Python 简介2.1 Python 的优点2.2 Python 的缺点2.3 Python 的主要应用领域 三、Python 就业前景为什么 Python 不适合找工作?学习目标 四、Python 学习路线4.1 Python 核心语法4.2 开发环境4.3 Python 教程4.4 视频教程4.5 学习书籍 五、Python 学习资料 大家好,今天为大

打工人最适合用AI做自媒体的6个赛道!AI绘画学习路线及学习资料整合!

最近听说国内又有了一个振奋人心的消息,那就是国内的AI技术巨头们纷纷推出了以极低价格开放的大模型API服务,这无疑为自媒体创作者和独立开发者们带来了一股春风。 第一个大家用AI不需要花费太多的钱,像chatGPT plus每个月20美金,对于很多软件来说还是有点贵了,关键这个还限制V4的使用次数。 虽然国内的大模型在技术水平上可能尚未达到GPT4的高度,但对于大部分应用场景来说,已经足够满足需

大模型产品经理学习路线,2024最新,从零基础入门到精通,非常详细收藏我这一篇

随着人工智能技术的发展,尤其是大模型(Large Model)的兴起,越来越多的企业开始重视这一领域的投入。作为大模型产品经理,你需要具备一系列跨学科的知识和技能,以便有效地推动产品的开发、优化和市场化。以下是一份详细的大模型产品经理学习路线,旨在帮助你构建所需的知识体系,从零基础到精通。 一、基础知识阶段 1. 计算机科学基础 数据结构与算法:理解基本的数据结构(如数组、链表、树、图等)和

数据结构____二叉树初阶

一:二叉树的基本概念和性质 1. 满二叉树:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为K,且结点总数是 ,则它就是满二叉树。 2. 完全二叉树:完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的点一一对应时称之为完全二叉树