PAT甲级-1072 Gas Station (30分)(迪杰斯特拉算法即可,DFS会超时)
发布日期:2022-02-10 08:10:57 浏览次数:18 分类:技术文章

本文共 3312 字,大约阅读时间需要 11 分钟。

题目:
分析:路径问题,用DFS会超时,使用迪杰斯特拉得出dis数组即可。注意!!!有个小坑:station不只是1-9,有可能是两位数以上,10,11,等等,因此在输入的时候字符串的处理要注意,不然最后一个测试点会报错。

AC代码(dj):

#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define MAX 999999999typedef long long ll;using namespace std;int n,m,k,ds;double road[10020][10020];int visi[10020];double dis[10020];//1-1000 1001-1010//每个候选加油站的距离住宅的所有最小中选一个最大的//必须保证所有住宅在加油站的服务范围//有多个选择的话,选平均距离到住宅最小的,还有多个选序号最小的void dj(int root){ fill(dis,dis+10020,MAX); dis[root] = 0; for(int i = 1; i <= n+m ;i++) { int u = -1; int mm = MAX; for(int j = 1;j<=n+m;j++) { if(dis[j] < mm && !visi[j]) { u = j; mm = dis[j]; } } visi[u] = 1; for(int j = 1;j <= n+m;j++) { if(!visi[j] && road[u][j] != 0 && dis[u] + road[u][j] < dis[j]) dis[j] = dis[u] +road[u][j]; } }}int main(){ cin>>n>>m>>k>>ds; for(int i = 1;i<=k;i++) { string a,b; int x,y; double c; cin>>a>>b>>c; if(a[0] == 'G') x = n + stoi(a.substr(1,a.size()-1)); else x = stoi(a); if(b[0] == 'G') y = n + stoi(b.substr(1,b.size()-1)); else y = stoi(b); road[x][y] = road[y][x] = c; } int idx = -1; double max_dis = -1; double avg_dis ; for(int i = n + 1;i <= n + m;i++) { int flag = 0; fill(visi,visi+10020,0); double c_avg_dis = 0; double min_dis = MAX; dj(i); for(int j = 1;j<=n;j++){ c_avg_dis += dis[j]; if(dis[j] < min_dis) min_dis = dis[j]; if(dis[j] > ds) flag = 1; } if(flag) continue;//超出服务范围 if(min_dis > max_dis) { max_dis = min_dis; avg_dis = c_avg_dis; idx = i; } else if(min_dis == max_dis && c_avg_dis < avg_dis) { avg_dis = c_avg_dis; idx = i; } } if(idx == -1) { cout<<"No Solution"; return 0; } cout<<"G"<
<

超时代码(DFS):

#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define MAX 999999999typedef long long ll;using namespace std;int n,m,k,ds;double road[10020][10020];int visi[10020];double dis[10020];//1-1000 1001-1010//每个候选加油站的距离住宅的所有最小中选一个最大的//必须保证所有住宅在加油站的服务范围//有多个选择的话,选平均距离到住宅最小的,还有多个选序号最小的double max_dis = -1;double avg_dis;double min_dis = MAX;double c_dis;void dfs(int root){ visi[root] = 1; if(c_dis < min_dis && c_dis != 0 && root >=1 && root <= n)//找出当前加油站距离最近的一个住宅的距离 min_dis = c_dis; if(c_dis < dis[root] && c_dis != 0 && root >=1 && root <= n)//得出dis数组的值,为距离每个住宅的最近距离 dis[root] = c_dis; for(int i = 1;i <= n + m;i++) { if(!visi[i] && road[root][i] != 0) { c_dis += road[root][i]; dfs(i); c_dis -= road[root][i]; } } visi[root] = 0;}int main(){ cin>>n>>m>>k>>ds; for(int i = 1;i<=n;i++) dis[i] = MAX; for(int i = 1;i<=k;i++) { string a,b; int x,y; double c; cin>>a>>b>>c; if(a[0] == 'G') x = n + stoi(a.substr(1,a.size()-1)); else x = stoi(a); if(b[0] == 'G') y = n + stoi(b.substr(1,b.size()-1)); else y = stoi(b); road[x][y] = road[y][x] = c; } int idx =-1; for(int i = n + 1;i <= n + m;i++) { fill(dis+1,dis+1+n,MAX); int flag = 0; double c_avg_dis = 0; min_dis = MAX; dfs(i); for(int j = 1;j<=n;j++){ c_avg_dis += dis[j]; if(dis[j] > ds) flag = 1; } if(flag) continue;//超出服务范围 if(min_dis > max_dis) { max_dis = min_dis; avg_dis = c_avg_dis; idx = i; } else if(min_dis == max_dis && c_avg_dis < avg_dis) { avg_dis = c_avg_dis; idx = i; } } if(idx == -1) { cout<<"No Solution"; return 0; } cout<<"G"<
<

转载地址:https://blog.csdn.net/qq_43567222/article/details/113482775 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:word使用
下一篇:PAT甲级-1073 Scientific Notation (20 分)

发表评论

最新留言

感谢大佬
[***.8.128.20]2024年03月14日 08时06分27秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

php json常用方法吗,利用JS操作JSON常用方法(实用,图文教程) 2019-04-21
php 推送 微信墙,HTML5服务器端推送事件 解决PHP微信墙推送问题 2019-04-21
pass.php,lostpass.php 2019-04-21
php对数据库操作中delete的用法,MySQL Delete 2019-04-21
oracle选择器,jQuery 选择器理解 2019-04-21
oracle types.cursortype,深入解析Cursor和绑定变量 2019-04-21
取自然五年 oracle,ORACLE to_char() 函数获取自然周数 2019-04-21
linux远程写入文件,linux – rsyslog不会将远程消息写入特定主机的日志文件 2019-04-21
linux交叉编译器的下载,linux 下安装arm-linux-gnueabi交叉编译器 2019-04-21
linux安装gcc gdb 4.9.2,CentOS 6.5 编译安装 GCC 4.9.2 2019-04-21
谭浩强c语言程序设计 在线,计算机C语言程序设计谭浩强.pdf 2019-04-21
c语言的按键,c语言获得键盘的按键 2019-04-21
c语言用循环转换单词首字母,用c++实现将文本每个单词首字母转换为大写 2019-04-21
热传导方程的差分解法c语言,九热传导方程的差分解法.PPT 2019-04-21
c语言为什么传指针不传值,指针传值的小不解 2019-04-21
android 模拟器 启动,android开发之启动模拟器并安装游戏apk 2019-04-21
android png idat 还原,png IDAT数据块还原问题 2019-04-21
Vue打开动态html页面,vue.js中怎么打开新页面? 2019-04-21
html 内容写入数据库中,FoxPro数据库写入html文件中 2019-04-21
html audio语音播放器,HTML5-定制音频播放器-audio 2019-04-21