C语言BFS(5)___TT与魔法师(swustoj2464)

作者:网络    软件教程库   2020-05-20

description

    tt生活在一个充满魔法的国度,为了便于管理,国王请魔法师在一些重要的城市之间造出了“彩虹桥”!彩虹桥的特殊之处在于,可以从桥的一头瞬间移动到另一头。国王还请魔法师为彩虹桥设计出了通行证,通行证大致分成a,b,c三种,彩虹桥也对应a,b,c三种,每个彩虹桥可以识别的通行证最多为三种,每个人都拥有一个唯一类型的通行证,拥有通行证的人可以在对应的彩虹桥两头来回穿梭,如拥有a通行证的人只可以穿梭于可识别a通行证的彩虹桥。
    一天,tt因为有急事需要从城市1穿梭到城市n,显然,一种类型的通行证可能不能使他顺利的从城市1到城市n。于是他请巫师帮忙看能不能设计一张万能的通行证,使他可以穿梭任意彩虹桥。巫师心力交瘁,终于设计出一种可以变换的通行证,这张通行证被巫师用魔法药水浸泡了七七四十九天,凝结了巫师的全部智慧,终于拥有了神奇的变换功能,使得它在每次使用以后会自动的变成另一种类型的通行证,变换的顺序为a-b-c-a…..如此循环。假设刚开始的类型为a。请你告诉tt如果他利用这张魔法卡片能不能顺利的从1点到n点。当然,由于每次传送都需要支付一定费用,所以在有多条路径存在的情况下,请选择花费最少的一条。

input

   第一行为测试的组数t,每组测试样例第一行输入2个数n,m代表n个城市之间有m条彩虹桥(1=n=1000,0=m=n*n)。接下来m行,每行四个数字s t l c(s!=t,1=l=1000,1=c=3)代表城市s和t之间(1=s,t=n)需要l的通行费和c型(为了方便,我们用1,2,3分别代表通行证a,b,c的类型)通行证(所有数字均是正整数)。

output

如果tt能顺利的从城市1到城市n,输出最终的最小花费,否者输出-1

sample input

2
4 3
1 2 1 1
2 3 2 2
3 4 3 3 
4 3
1 2 1 1
2 3 2 2
3 4 3 2

sample output

6 
-1

原题链接: http://www.oj.swust.edu.cn/problem/show/2464



分析:

最开始想的是用记忆化搜索,然后无情的wa的很多次,然后只能随机生成数据跟ac代码对比跑,终于跑了几千组数据找到了原因,记忆化搜索在这道题出现的弊端就是如果路径顺序读取问题可能会导致过某个点a后到达另一个点b,假如存在一条从b到a再到n点的路径,这时候因为先到了a点,a被标记了,然后b就不能通过a到达n点,这个时候b的数据就被记忆化为不可到达终点。然而标记又不能取消,不然就会在环状地图进行死循环。这个问题只是记忆化搜索的问题之一,然而代码改了很多遍还是wa.

下面贴出记忆化搜索的代码:

#include cstdio
#include cstring
#include vector
#include iostream
#include queue
#include stdlib.h
using namespace std;
int memory[1001][1001][4],n,m;
int mpt[1001][1001][4],money[1001][1001][4];
bool book[1001][1001][4]; 
vectorintway[1001]; 
int min(int a,int b){
	return (ab) b:a;
}
int dfs(int pre,int step,int k){
	
	if(step==n)return 0;
	if(memory[pre][step][k])return memory[pre][step][k];
	book[pre][step][k]=true;
	int i,ans=999999999;
	for(i=0;iway[step].size();i++){
		//coutstep→ way[step][i]endl;
		//printf(book[%d][%d]=%d\n,way[step][i],k%3+1,book[way[step][i]][k%3+1]);
		if(mpt[step][way[step][i]][k]==0 || book[step][way[step][i]][k%3+1]==true)continue;
		//coutstep→ way[step][i] k:kendl;
		ans=min(ans,dfs(step,way[step][i],k%3+1)+money[step][way[step][i]][k]);
	}
	book[pre][step][k]=false;
	//printf(memort[%d][%d]=%d\n,step,k,ans); 
	if(ans!=999999999) 
	memory[pre][step][k]=ans;
	return ans;
} 
void init(){
	int i;
	for(i=0;i1001;i++) way[i].clear();
	memset(memory,0,sizeof(memory));
	memset(money,0,sizeof(money));
	memset(mpt,0,sizeof(mpt)); 
	memset(book,0,sizeof(book));
}
int main()
{
	int i,j,v,u,k,w,t,ans;
	cint;
	while(t--){
		cinnm;
		init();
		for(i=0;im;i++){
			scanf(%d%d%d%d,v,u,w,k);
			if(mpt[v][u][1]==0  mpt[v][u][2]==0  mpt[v][u][3]==0){
			way[v].push_back(u);
			way[u].push_back(v);
			}
			if(money[v][u][k]==0) money[v][u][k]=w,money[u][v][k]=w;
			else{
				money[v][u][k]=min(money[v][u][k],w);
				money[u][v][k]=min(money[u][v][k],w);
			}
			mpt[u][v][k]=mpt[v][u][k]=1; 
		}
		ans=dfs(0,1,1);
		if(ans!=999999999)printf(%d\n,ans);
		else printf(-1\n);

	} 
	return 0; 
 } 



然后用spfa来做这道题:

#include cstdio
#include cstring
#include vector
#include iostream
#include queue
#include stdlib.h
using namespace std;
struct node
{
	int data,v,w;
};
struct node1
{
	int step,v;
};
int n,m;
int visit[1001][4],dis[1001][4];  //visit数组是记录当前状态 [节点编号][通行证编号]是否在队列中.
vectornodempt[1001];
void spfa()
{
	node1 s,e;
	int i,j,ss;
	queuenode1team;
	s.step=1;s.v=1;
	team.push(s);
	visit[1][1]=1;
	while(team.size()){   //用队列中的状态去更新最小花费.
		s=team.front();
		team.pop();
		visit[s.step][s.v]=0;
		ss=mpt[s.step].size();
		for(i=0;iss;i++){
			if(mpt[s.step][i].v!=s.v)continue;
			if(dis[s.step][s.v]+mpt[s.step][i].w=dis[mpt[s.step][i].data][s.v%3+1])continue; 
			dis[mpt[s.step][i].data][s.v%3+1]=dis[s.step][s.v]+mpt[s.step][i].w;  //松弛
			if(visit[mpt[s.step][i].data][s.v%3+1]!=0)continue;
			e.step=mpt[s.step][i].data;
			e.v=s.v%3+1;
			visit[e.step][e.v]=1;
			team.push(e);
		}
	}
	int min=1999999999;
	for(i=1;i4;i++)if(mindis[n][i])min=dis[n][i];
	if(min!=1999999999)coutminendl;
	else cout-1endl;
 } 
int main()
{
	int i,j,t,x,y;
	cint;
	while(t--){
		cinnm;
		memset(visit,0,sizeof(visit));
		for(i=1;i=n;i++)for(j=0;j4;j++)dis[i][j]=1999999999;
		dis[1][1]=0;
		for(i=0;i1001;i++)mpt[i].clear(); 
		for(i=0;im;i++){
			node s;
			cinxys.ws.v;
			s.data=x;
			mpt[y].push_back(s);
			s.data=y;
			mpt[x].push_back(s);
		}
		spfa();
	}
	return 0;
}

如果有大神能用记忆化搜索做出来麻烦贴在下面的评论一下,万分感谢!!!!




c语言bfs(5)___tt与魔法师(swust oj 2464)

原文地址:http://blog.csdn.net/y1196645376/article/details/45422497

以上就是由(软件教程库https://www.itjcku.com/9999/1091530.html)本站为大家整理

阅读全部内容


Tags:语言魔法师

返回首页



推荐内容

进程类Process与多线程Thread

进程类(process)的基本操作: //通过进程类查询系统所有进程 process[] pr ...

Xml解析方式之Pull解析器的使用

xml有多种解析的方式,这篇文章只介绍用pull解析器来解析xml文件,接下来我会说明使用pull解析器来读取xml文件 ...

enum,EnumMap,EnumSet

enum基本使用 : package com.enumtest; enum shrubbery { gr ...

Hibernate乱码问题解决

乱码问题其实归根接地就是两端的字符集不统一。 解决思路也有两种: 1. 修改两端字符集统一。 2. 通过代码进行转 ...

eclipse集成struts2.3.20

需要强调的是,这里介绍的是在eclipse工具下集成struts2.3.20而不是myeclipse添加对struts2 ...

ubi文件系统制作,还是"-c"选项的问题

以下是分析记录: --------------------------------------------------- ...

如何把事情做到最好读书笔记1

开篇语: 每个人生来都具备足够的潜力,每个人都能做到别人#30524;中难以企及的事情。请永远保持初学之心,勇敢面对 ...

如何把事情做到最好读书笔记2

第二章 认清自己:你属于哪种类型的人 你必须足够了解你自己,下面有三种类型的人、 (1)浅尝辄止者 浅尝辄止者对一切 ...

如何把事情做到最好读书笔记3

第三章 一份耕耘才能一份收获 当你决定踏上精益求精之路时,你会突然发现周围的一切都与你所追求的#26684;#2668 ...

如何把事情做到最好读书笔记4

第四章 热爱平台期 从小,我们接受的教育就是好好学习,这样才能上好的大学,上好的大学才能找到好工作,有好工作才能有钱买 ...

习题10-21二项式系数UVa1649

1.题目描述:点击打开链接 2.解题思路:本题利用枚举#43;二分解决。问题的关键是选对枚举对象,因为要找c(n,k)= ...

mysql小技巧

selectnow(),user(),version(),database(); #最后输入\c是放弃的意思 des ...

Java学习笔记——面试常客:写出一个死锁的例子

现在的面试挺蛋疼,为了考察大家的语言掌握水平,类#20284;这样的题特别多,不过在某个角度来说确实能看出一个人对某个知 ...

UVA-10396VampireNumbers暴力+打表

题目大意:给出n,要求你输出所有符合规则的n位数 规则如下,这个n位数由两个n/2位数相乘得到,并且满足 1.这n位 ...

CF148D.Bagofmice[概率dp]

题目链接:http://codeforces.com/problemset/problem/148/d 题目大意:一袋子 ...

HDU-1846-BraveGame(巴什博弈)

题目传送:brave game 介绍: 巴什博奕(bash game): 首先我们来玩一个比较古老的报数游戏。a ...

HDU-2149-PublicSale(巴什博弈)

题目传送:public sale 思路:巴什博弈 ac代码: #include lt;cstdiogt; # ...

enum实现售卖机

首先 推荐一下google的代码风格 :https://google-styleguide.googlecode ...

批量添加用户

a、创建用户文件,因为添加的用户比较多,因此编写脚本创建一个用户文件user.txt #!/bin/ba ...

解决侧滑中ViewPager和SlidingMenu的滑动冲突

当我们在使用开源框架slidingmenu时,如果要是使用到viewpager,就会出现滑动冲突。 解决方案: }/** ...

shell打乱文件行

思路,产生一个随机数组,然后按按照数组的元素将文件中行的重新输出 1、随机数组的生成 看书的时候感觉很是简单。第 ...

编程之美2015初赛第二场AB

题目1 : 扑克牌 时间限制:2000ms 单点时限:1000ms 内存限制:256mb 描述 一副不含王的扑 ...

Java设计模式之单例模式(恶汉式和懒汉式)

/* * 单例模式: * 饿汉式:类一加载就创建对象 * 懒汉式:用的时候,才去创建对象 * 面试题:单例模式的 ...

Html简单介绍

1、html--- hypertext markup language 的缩写 --- 超文本 标记 语言. 这个技 ...

configure:error:youmustconfigureinaseparatebuilddirectory

configure glibc-2.14 时出现以下错误: [[email#160;protected] opt]# ...

kohana框架生成feed

创建feed feed::create()斱法用给定癿参数杢创建 rss戒者 atom feed。下面是可接叐癿参数。 ...

用USB安装linux

手边没有光驱,安装ubuntu可以用 linuxlive usb creator 2.9.3,在百度网盘里有的。http ...

一个复杂子查询SQL优化

select * from test.vmark vk where id in (select v.id ...

Java多线程中常见的几个问题

我们都知道,在java中要想实现多线程,有两种手段,一种是继续thread类,另外一种是实现runable接口。  1. ...

OracleDataIntegrator12c-CreatingaCollocatedAgent

http://www.oracle.com/webfolder/technetwork/tutorials/obe/fm ...


本网站部分内容来自互联网,版权归原作者所有,文章内容仅代表原作者个人观点。如有侵权请联系我们删除 电子邮件 itjcku@foxmail.com