poj_3767——I Wanna Go Home

2024-01-04 09:48
文章标签 go poj home 3767 wanna

本文主要是介绍poj_3767——I Wanna Go Home,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

来源:http://poj.org/problem?id=3767

题目就不贴了,把代码和遇到的问题分享一下吧!

中间用G++交了很多次都是RE(运行错误),后来改用C++交发现还是有问题,一样的错误。这个程序中发现我写的一般都是用C++交比较牢靠,还有定义迪杰斯特拉 函数名的时候我用了个dijk(),然后我悲剧了,RE!你懂得,后来突发奇想改了一下交上去就AC了。郁闷死我啊!


呵呵,废话说完,下面说一下这个题,这个题目其实就是最短路的应用,在这里用的还是挺简单的,把迪杰斯特拉算法掌握就OK!

由于这个题中从1类城市走到2类城市后就不能再回去,只能穿过一次,所以先存为双向路,后面再根据不同类型的城市,把双向路变为单向路。

然后核心算法实现就OK!

代码:

#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
#define inf 0xfffffff
#define size 610
int value[size][size];
int d[size];
int lead[size];
bool visit[size];
int n,m;
void djk()
{int x,y,z,tab,temp;memset(visit,0,sizeof(visit));for(x=1;x<=n;x++)d[x]=value[1][x];d[1]=0;visit[1]=1;for(x=1;x<n;x++){temp=inf;for(y=1;y<=n;y++){if(!visit[y]&&d[y]<temp){temp=d[y];tab=y;}}visit[tab]=true;for(z=1;z<=n;z++){if(!visit[z]&&d[z]>d[tab]+value[tab][z])d[z]=d[tab]+value[tab][z];}}if(d[2]==inf)cout<<"-1\n";elsecout<<d[2]<<endl;
}int main()
{while(cin>>n){if(n==0)break;int i,j,a,b,len;cin>>m;memset(lead,0,sizeof(lead));for(i=1;i<=n;i++)for(j=1;j<=n;j++)value[i][j]=inf;for(i=1;i<=m;i++){cin>>a>>b>>len;value[a][b]=value[b][a]=len;}for(i=1;i<=n;i++)cin>>lead[i];for(i=1;i<=n;i++){for(j=1;j<=n;j++){if(lead[i]!=lead[j]){if(lead[i]==1&&lead[j]==2)value[j][i]=inf;else if(lead[i]==2&&lead[j]==1)value[i][j]=inf;}}}djk();}return 0;
}
在执行后面双向图转换单向图时有另外一种方法,

但是交上去也是RE。

for(i=1;i<=n;i++){if(lead[i]==2){for(j=1;j<=n;j++){if(lead[j]==1)value[i][j]=inf;}}}

很悲剧啊!

这篇关于poj_3767——I Wanna Go Home的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

go动态限制并发数量的实现示例

《go动态限制并发数量的实现示例》本文主要介绍了Go并发控制方法,通过带缓冲通道和第三方库实现并发数量限制,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面... 目录带有缓冲大小的通道使用第三方库其他控制并发的方法因为go从语言层面支持并发,所以面试百分百会问到

Go语言并发之通知退出机制的实现

《Go语言并发之通知退出机制的实现》本文主要介绍了Go语言并发之通知退出机制的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录1、通知退出机制1.1 进程/main函数退出1.2 通过channel退出1.3 通过cont

Go语言编译环境设置教程

《Go语言编译环境设置教程》Go语言支持高并发(goroutine)、自动垃圾回收,编译为跨平台二进制文件,云原生兼容且社区活跃,开发便捷,内置测试与vet工具辅助检测错误,依赖模块化管理,提升开发效... 目录Go语言优势下载 Go  配置编译环境配置 GOPROXYIDE 设置(VS Code)一些基本

使用Go实现文件复制的完整流程

《使用Go实现文件复制的完整流程》本案例将实现一个实用的文件操作工具:将一个文件的内容完整复制到另一个文件中,这是文件处理中的常见任务,比如配置文件备份、日志迁移、用户上传文件转存等,文中通过代码示例... 目录案例说明涉及China编程知识点示例代码代码解析示例运行练习扩展小结案例说明我们将通过标准库 os

深入理解Go语言中二维切片的使用

《深入理解Go语言中二维切片的使用》本文深入讲解了Go语言中二维切片的概念与应用,用于表示矩阵、表格等二维数据结构,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起学习学习吧... 目录引言二维切片的基本概念定义创建二维切片二维切片的操作访问元素修改元素遍历二维切片二维切片的动态调整追加行动态

go中的时间处理过程

《go中的时间处理过程》:本文主要介绍go中的时间处理过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1 获取当前时间2 获取当前时间戳3 获取当前时间的字符串格式4 相互转化4.1 时间戳转时间字符串 (int64 > string)4.2 时间字符串转时间

Go语言中make和new的区别及说明

《Go语言中make和new的区别及说明》:本文主要介绍Go语言中make和new的区别及说明,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1 概述2 new 函数2.1 功能2.2 语法2.3 初始化案例3 make 函数3.1 功能3.2 语法3.3 初始化

Go语言中nil判断的注意事项(最新推荐)

《Go语言中nil判断的注意事项(最新推荐)》本文给大家介绍Go语言中nil判断的注意事项,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1.接口变量的特殊行为2.nil的合法类型3.nil值的实用行为4.自定义类型与nil5.反射判断nil6.函数返回的

Go语言数据库编程GORM 的基本使用详解

《Go语言数据库编程GORM的基本使用详解》GORM是Go语言流行的ORM框架,封装database/sql,支持自动迁移、关联、事务等,提供CRUD、条件查询、钩子函数、日志等功能,简化数据库操作... 目录一、安装与初始化1. 安装 GORM 及数据库驱动2. 建立数据库连接二、定义模型结构体三、自动迁

Go语言代码格式化的技巧分享

《Go语言代码格式化的技巧分享》在Go语言的开发过程中,代码格式化是一个看似细微却至关重要的环节,良好的代码格式化不仅能提升代码的可读性,还能促进团队协作,减少因代码风格差异引发的问题,Go在代码格式... 目录一、Go 语言代码格式化的重要性二、Go 语言代码格式化工具:gofmt 与 go fmt(一)