201712-4行车路线

2023-12-15 13:18
文章标签 路线 行车 201712

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

 

一、问题描述

试题编号：201712-4
试题名称：行车路线
时间限制：1.0s
内存限制：256.0MB
问题描述：

问题描述

　　小明和小芳出去乡村玩，小明负责开车，小芳来导航。
　　小芳将可能的道路分为大道和小道。大道比较好走，每走1公里小明会增加1的疲劳度。小道不好走，如果连续走小道，小明的疲劳值会快速增加，连续走s公里小明会增加s2的疲劳度。
　　例如：有5个路口，1号路口到2号路口为小道，2号路口到3号路口为小道，3号路口到4号路口为大道，4号路口到5号路口为小道，相邻路口之间的距离都是2公里。如果小明从1号路口到5号路口，则总疲劳值为(2+2)2+2+22=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号路口是连通的。

输出格式

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

样例输入

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，疲劳度为52=25；然后从3走大道经过4到达5，疲劳度为20+30=50；最后从5走小道到6，疲劳度为1。总共为76。

数据规模和约定

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

二、分析解答

说一说吧，其实一开始我就做对了，不过时间复杂度比较高，然后就瞎改，80分是因为我的那个算长度是一个函数特别复杂，然后好像是递归的，反正很慢。中间错了一堆是因为，我想把三个版本的函数几乎两两结合看看是哪里错了，然后就发现了一些我也不清楚的东西，总之乱改一通，其实都什么都没用。

没办法这题我干不动。只有90分，剩下的应该是超时，不会nlogn的代码。这是版本三。看着办吧，我好差劲一点也不会。

#include <iostream>
#include <climits>
#include <queue>
using namespace std;
#define INF LONG_LONG_MAX
#define MAX_NODE 505
#define BG 0
#define SM 1
#define NONE 2
///node,edge
int n_node,m_edge;
///edge
int t_type,a_start,b_end;
long long c_len;
///road
long long len[MAX_NODE][MAX_NODE];
int type[MAX_NODE][MAX_NODE];
int path[MAX_NODE];
long long tired[MAX_NODE];
long long before_sm[MAX_NODE];
long long last_sm[MAX_NODE];
void init_path_dist(int i){if(type[0][i]!=NONE){path[i]=0;tired[i]=(type[0][i] == BG ? len[0][i] : len[0][i]*len[0][i]);before_sm[i]=(type[0][i] == BG ? len[0][i] : 0);last_sm[i]=(type[0][i] == BG ? 0 : len[0][i]);}else{path[i]=-1;tired[i]=INF;}
}
long long dij(){priority_queue<node> que;///put 0 in the the setint i,j;int flag[n_node]={};for(i=0;i<n_node;i++){init_path_dist(i);}flag[0]=1;///put n-1 node in the setfor(i=0;i<n_node-1;i++){///explore: find mindist node from not in and make it in.long long mindist=INF,minindex=-1;for(j=0;j<n_node;j++){if(flag[j]==0&&tired[j]<mindist){minindex=j;mindist=tired[j];}}if(mindist>=INF)break;flag[minindex]=1;///exploit:will the node reduce the dist?for(j=0;j<n_node;j++){if(flag[j]==0&&type[minindex][j]!=NONE){long long newdist=INF,t_last_sm=0,t_before=before_sm[minindex];if(type[minindex][j]==BG){newdist=tired[minindex]+len[minindex][j];t_before=newdist;}else if(type[minindex][j]==SM){newdist=before_sm[minindex]+(last_sm[minindex]+len[minindex][j])*(last_sm[minindex]+len[minindex][j]);t_last_sm=last_sm[minindex]+len[minindex][j];}///cout<<minindex+1<<" "<<j+1<<" "<<" before:"<<before_sm[minindex]<<" last:"<<last_sm[j]<<" len:"<<len[minindex][j]<<" "<<newdist<<" "<<tired[j]<<endl;if(newdist<tired[j]){path[j]=minindex;tired[j]=newdist;before_sm[j]=t_before;last_sm[j]=t_last_sm;}}}//for(j=0;j<n_node;j++){//cout<<path[j]<<" ";//}cout<<endl;}return tired[n_node-1];
}
int main()
{///inputcin>>n_node>>m_edge;///initint i,j;for(i=0;i<n_node;i++){for(j=0;j<n_node;j++){if(i==j){len[i][j]=0;type[i][j]=BG;}else{len[i][j]=INF;type[i][j]=NONE;}}}///inputfor(i=0;i<m_edge;i++){cin>>t_type>>a_start>>b_end>>c_len;a_start--;b_end--;len[a_start][b_end]=len[b_end][a_start]=c_len;type[a_start][b_end]=type[b_end][a_start]=t_type;}cout << dij();return 0;
}

 

这也是我的90分代码，版本二。

#include <cstdio>
#include <iostream>
#include <climits>
using namespace std;
#define INF LONG_LONG_MAX
#define BG 0
#define SM 1
#define NONE 2
#define MAX_NODE 505
#define MAX_EDGE 100005
///node,edge
int n_node,m_edge;
///edge
int t_type,a_start,b_end;
long long c_len;
///road
typedef struct ROAD{long long len[MAX_NODE][MAX_NODE];int type[MAX_NODE][MAX_NODE];int path[MAX_NODE];long long tir[MAX_NODE];long long l_sm[MAX_NODE];
}Road;
Road road;
///end!=0
long long dist(int end){///not connectif(road.path[end]==-1){return INF;}int i,j;int last_type=NONE;long long sum=0,tmp=0;for(i=end;i!=0;i=j){j=road.path[i];if(last_type==NONE){tmp=road.len[j][i];last_type=road.type[j][i];continue;}if(road.type[j][i]!=last_type){if(last_type==BG){sum+=tmp;}else if(last_type==SM){sum+=(tmp*tmp);}last_type=road.type[j][i];tmp=road.len[j][i];}else{last_type=road.type[j][i];tmp+=road.len[j][i];}}if(last_type==BG){sum+=tmp;}else if(last_type==SM){sum+=(tmp*tmp);}return sum;
}
///mid!=0
long long dist_mid(int mid,int next){long long lenn=0;int tmp=road.path[next];road.path[next]=mid;lenn=dist(next);road.path[next]=tmp;return lenn;
}
///0->n-1
long long dij(){///initint i,j;for(i=0;i<n_node;i++){if(road.len[0][i]<INF){road.path[i]=0;}else{road.path[i]=-1;}}///put in n nodeint flag[n_node]={};flag[0]=1;for(i=0;i<n_node-1;i++){///find mindist from not in and make it in.explore!long long mindist=INF,minindex=-1;for(j=0;j<n_node;j++){if(flag[j]==0&&dist(j)<mindist){minindex=j;mindist=dist(j);}}if(mindist>=INF)break;flag[minindex]=1;///is there some change?exploit!for(j=0;j<n_node;j++){if(flag[j]==0&&road.len[minindex][j]!=INF&&dist_mid(minindex,j)<dist(j)){road.path[j]=minindex;}}}return dist(n_node-1);
}int main(){///inputcin>>n_node>>m_edge;///initint i,j;for(i=0;i<n_node;i++){for(j=0;j<n_node;j++){if(i==j){road.len[i][j]=0;road.type[i][j]=NONE;}else{road.len[i][j]=INF;road.type[i][j]=NONE;}}}///inputfor(i=0;i<m_edge;i++){cin>>t_type>>a_start>>b_end>>c_len;a_start--;b_end--;road.len[a_start][b_end]=road.len[b_end][a_start]=c_len;road.type[a_start][b_end]=road.type[b_end][a_start]=t_type;}long long tired = dij();cout << tired;return 0;
}

还有这个，是版本一，也是90分。

#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
#define INF 0x3f3f3f3f
#define BG 0
#define SM 1
#define MAX_NODE 505
#define MAX_EDGE 100000
///node,edge,
int n_node,m_edge;
///edge
long long t_type,a_start,b_end,c_len;
///road
typedef struct ROAD{long long len[MAX_NODE][MAX_NODE];int type[MAX_NODE][MAX_NODE];int path[MAX_NODE];
}Road;Road road;long long dist(int end){if(road.path[end]==-1){return INF;}int i,j;int last_type=-1;long long sum=0,tmp=0;for(i=end;i!=0;i=j){j=road.path[i];if(road.type[j][i]!=last_type){if(last_type==BG){sum+=tmp;}else if(last_type==SM){sum+=(tmp*tmp);}else{tmp=road.len[j][i];last_type=road.type[j][i];continue;}tmp=0;}last_type=road.type[j][i];tmp+=road.len[j][i];}if(last_type==BG){sum+=tmp;}else if(last_type==SM){sum+=(tmp*tmp);}//cout<<sum;return sum;
}
long long dist_mid(int mid,int next){if(road.len[mid][next]==INF){return INF;}int x=road.path[mid];long long lenn=0;if(road.type[mid][next]==road.type[x][mid]){int m=road.path[next];road.path[next]=mid;lenn=dist(next);road.path[next]=m;}else{lenn=dist(mid)+road.len[mid][next];}return lenn;
}///0->n-1
long long dij(){int i,j;for(i=0;i<n_node;i++){if(road.len[0][i]<INF)road.path[i]=0;elseroad.path[i]=-1;}///put in n nodeint flag[n_node]={};flag[0]=1;for(i=0;i<n_node-1;i++){///find mindist from not in and make it in.explore!long long mindist=INF,minindex=-1;for(j=0;j<n_node;j++){if(flag[j]==0&&dist(j)<mindist){minindex=j;mindist=dist(j);}}///cout<<minindex<<" "<<mindist<<endl;flag[minindex]=1;///is there some change?exploit!for(j=0;j<n_node;j++){if(mindist!=INF&&flag[j]==0&&dist_mid(minindex,j)<dist(j)){road.path[j]=minindex;}}}
//    for(i=0;i<n_node;i++){
//        cout<<road.path[i]<<" "<<dist(i)<<endl;
//    }return dist(n_node-1);
}int main(){///inputcin>>n_node>>m_edge;int i,j;for(i=0;i<n_node;i++){for(j=0;j<n_node;j++){if(i==j){road.len[i][j]=0;road.type[i][j]=0;}else{road.len[i][j]=INF;road.type[i][j]=-2;}}}for(i=0;i<m_edge;i++){cin>>t_type>>a_start>>b_end>>c_len;a_start--;b_end--;road.len[a_start][b_end]=road.len[b_end][a_start]=c_len;road.type[a_start][b_end]=road.type[b_end][a_start]=t_type;}long long tired = dij();cout << tired;return 0;
}

 

这篇关于201712-4行车路线的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/496586。

相关文章

大模型的学习路线（非常详细）神仙级教程，手把手教会你

大模型的学习路线（非常详细）神仙级教程，手把手教会你

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

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

前言 专门为C#/.NET/.NET Core推荐学习路线&文档&文章提供的一个Issues，各位小伙伴可以把自己觉得不错的学习路线、文档、文章相关地址分享出来🤞。 https://github.com/YSGStudyHards/DotNetGuide/issues/10 🏷️C#/.NET/.NET Core优质学习资料 📚.NET 入门教程 📚
阅读更多...
龙蜥社区首推 AI 原生操作系统路线，三大重磅计划协同生态布局未来

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

近日，2024 龙蜥操作系统大会（OpenAnolis Conference）在北京圆满召开，此次大会由中国计算机学会开源发展委员会、中关村科学城委员会、海淀区委网信办、中国开源软件推进联盟指导，龙蜥社区主办，阿里云、浪潮信息、Intel、中兴通讯、Arm、中科方德等 24 家理事单位共同承办，主题为“进化·重构·赴未来”。北京市委网信办、海淀区委网信办等领导莅临指导，中国工程院院士、浙江大学信息
阅读更多...
2024最全自学黑客技术学习路线，带你少走一点弯路！

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

谈起黑客，可能各位都会想到：盗号，其实不尽然；黑客是一群喜爱研究技术的群体，在黑客圈中，一般分为三大圈：娱乐圈 技术圈 职业圈。 娱乐圈：主要是初中生和高中生较多，玩网恋，人气，空间，建站收徒玩赚钱，技术高的也是有的，只是很少见。 技术圈：这个圈子里面的黑客是为了能把黑客技术玩到极致的技术狂人，我最佩服的就是这群人，希望以后自己也能成为这样的人。 职业圈：这里面的人群主要就是玩HC为主了
阅读更多...
2024 年 Python 学习路线推荐，附学习书籍，学习视频（建议收藏）

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做自媒体的6个赛道！AI绘画学习路线及学习资料整合！

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

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

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

【深度学习 CV方向】图像算法工程师 职业发展路线，以及学习路线

图像算法工程师的职业发展路线通常可以分为以下几个阶段： 初级图像算法工程师： 技能要求：掌握基本的图像处理算法和编程能力，能够在指导下完成简单的图像算法项目。对于常见的图像算法，如滤波、边缘检测、图像分割等有一定的了解，并能够使用相关的编程工具和库进行实现。工作内容：主要负责一些基础的图像算法开发和优化工作，可能会参与到一些小型项目中，承担部分模块的开发任务。同时，需要不断学习和积累经验，提升自
阅读更多...
个人旅游网(3)——功能详解——旅游路线功能

个人旅游网(3)——功能详解——旅游路线功能

文章目录 一、旅游路线分类功能1.1、接口详解1.1.1、findAll 二、路线分类下的旅游路线功能2.2、接口详解2.2.1、findRouteListByCid 三、点击单条旅游路线查看其详情功能3.1、接口详解3.1.1、findRouteListByRid 四、分页功能4.1、导入依赖4.2、配置项的配置4.3、实现分页 一、旅游路线分类功能 页面效果图： 上
阅读更多...
求教0基础入门大模型的学习路线?LLM大模型学习教程

求教0基础入门大模型的学习路线?LLM大模型学习教程

0基础入门大模型，transformer、bert这些是要学的，但是你的第一口不一定从这里咬下去。 真的没有必要一上来就把时间精力全部投入到复杂的理论、各种晦涩的数学公式还有编程语言上，这样不仅容易让你气馁，而且特别容易磨光热情。 当我们认识复杂新事物时，最舒适的路径应当是：感性认识现象->理解本质和原理->将所学知识用于解释新现象并指导实践。 所以我给出的这条路径是：先学会如何使用大模型，
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2