Oj.Nbdp.Net
初赛题库
问题
状态
排名
团队
题解
课程
Login
问题 3377 --小胖抗日
3377: 小胖抗日
警告！
题目
状态
题解(2)
题目描述
对于窃取情报和破译密码，huyichen简直就是天才！在抗日作战中，huyichen已经多次成功的窃取日伪军的重要情报，为我军获取了大量作战取胜的关键筹码。 这天，huyichen又一次成功破译了对方的秘密电报。电报的内容为： 明天凌晨2：00，所有部队集中埋伏剿灭土八路3721整编军，天皇万福，保佑这次偷袭成功！ huyichen知道我军3721整编军是我军一支重点培养的生力军，如果在这次行动中遭受损失，那对我军将是一个十分严重的实力打击。这么重要的消息，必须赶紧传达到指挥部！由于抗战期间交通十分落后，huyichen只好委托xuzhenyi连夜将该消息送达总部。接到委托，xuzhenyi立即启程。 从情报站到指挥部之间有许多错综交叉的道路，道路和道路的交叉处都有地方可以供xuzhenyi躲藏。由于这里是交通要道，敌人也对这个地带十分关注：他们会时不时对在某些道路上派人巡逻。虽然xuzhenyi可以用精准的枪法将他们干掉，但是现在身负重任，不能打草惊蛇，所以必须避开他们。这意味着，如果某条道路有人巡逻，那么xuzhenyi将无法穿过。时间紧迫，xuzhenyi必须尽快到达总部。现在xuzhenyi再次向你求助，他应该如何行走才能用最短的时间到达指挥部。 说明：在每个交叉路口，xuzhenyi都能选择躲藏和行走。敌人的巡逻是周期循环的，他们总是以分钟为单位巡逻某条道路，在该分钟过去后离开。针对每条道路，我们假设xuzhenyi总是刚好用1分钟时间走完。 针对下列数据： V={1,2,3,4,5}; E={(1,2),(2,3),(3,4),(2,4),(4,5),(1,3),(3,5)} 结点1为情报站，5为指挥部，其余为交叉路口。 周期为4分钟。 每个周期的第1分钟有巡逻的边为{(1,2),(2,4),(4,5)} 每个周期的第2分钟有巡逻的边为{(1,3),(2,3),(3,5)} 每个周期的第3分钟有巡逻的边为{(3,4),(4,5)} 每个周期的第4分钟没有巡逻边。 这样，xuzhenyi可以在第一分钟走边(1,3)，第二分钟躲藏，第3分钟走边(3,5)，消耗3分钟，时间最短。
输入
每组输入数据第一行有2个整数n和m（1≤n≤100; 1≤m≤500），代表地图有n个结点m条边。1号结总是代表情报站，n号结点总是代表指挥部。 接下去m行是对地图的描述，每行有2个小于n的整数，分别代表一条边两端的结点编号。（如果边被重复描述，仍表示只有一条边）。 再接下去一行有一个整数k（0≤k≤10）代表周期长度。 后来的数据都是对周期巡逻边的描述，每行有2个整数，表示被关注的边。0 0则表示对周期中某一分钟的巡逻边描述结束。数据保证在该段恰存在k个0 0。
输出
输出数据仅有一行，如果xuzhenyi可以到达指挥部，则输出到达指挥部的最短时间。如果不能到达则输出“No solution.”
样例输入输出
输入#1
复制
5 7 1 2 2 3 3 4 2 4 4 5 1 3 3 5 4 1 2 2 4 4 5 0 0 1 3 2 3 3 5 0 0 3 4 4 5 0 0 0 0
输出#1
复制
3
提示
发表题解
序号
标题
作者
发表时间
费用
订购数
操作
题目信息
提交
难度
提高+/省选-
标签
深搜
点击显示
递交数
22
已通过
16
通过率
73%
时间限制
1 秒
内存限制
128 MB
来源
小胖系列
收藏
标签云
模拟
数学与数论
动态规划
贪心
字符串
排序
枚举
数组与串
深搜
高精度
循环结构
递推
递归
二分三分
宽搜
背包
质数
线段树
分治
N进制
图论
队列
最短路
堆
树
并查集
栈
状态压缩
分支结构
几何
博弈论
生成树
顺序结构
离散化
hash表
位运算
单调队列
树状数组
KMP
字典树
二分图
数学期望
AC自动机
树链剖分
差分约束
数位动态规划
函数与过程
网络流
单调栈
前缀和