2 shunfurh shunfurh 于 2017.09.02 22:13 提问

Color Tunnels

A company producing toys has a complex system to paint its products. To obtain the desired color, the product must be painted by several colors in a specified order. A product is painted by moving through color tunnels. For each color there is at least one tunnel that paints with that color, but there may be more. The tunnels are distributed in the painting area and the product must be delivered from one tunnel to another in order to be painted with the given colors. The product is at a certain point in the production plant when painting process starts and must finally be delivered to the product warehouse.
More formally, a finished uncolored product is at a certain given point (source point) and must be delivered to another given point (destination point) after being painted with different colors in a given order. There are several tunnels, each is assumed to be a line segment in the plain with a specific color. The colors of the tunnels are not necessarily distinct. Let be the sequence of n colors that the product is to be painted with. The product is required to pass through tunnels such that the color of ti is ci. Note that it is possible to pass through a tunnel without being painted, so the mentioned may be in fact a subsequence of the tunnels which the product passes through. The direction in which the product passes a tunnel is not important. The goal is to find the shortest path from source to destination subject to the color constraints. The path may cross itself, or even cross a tunnel. Passing twice (or more) through a tunnel is also allowed. Note that two tunnels can cross or overlap but are different.

Input

The input file contains several test cases. The first line of the input consists of a single integer t (between 1 and 20), the number of test cases. Following the first line is the data for t test cases. The first line of each test case contains four real numbers xs, ys, xt, yt which are x and y coordinates of the source and destination respectively. The second line of the test case contains the color sequence: the first number is the length of the sequence (between 1 and 30), and the rest of the line is the sequence itself. Each color in the sequence is an integer in the range 1...100. The third line contains a single integer n in the range 1...60 which is the number of tunnels followed by n lines each containing five numbers. The first two numbers are the x and y coordinates of one end of the tunnel. The third and fourth numbers are the x and y coordinates of the other end. Coordinates are real numbers. The fifth number is an integer in the range 1...100 representing the color of the tunnel.

Output

The output file must have t lines, each containing the minimum length of a path from source to destination subject to the constraints of the problem. The length will be compared to optimal length within a precision of three digits after decimal point.

Sample Input

1
0 1.5 100 67
4 1 4 3 1
9
10 10 20 20 1
10 15 20.5 35.333 3
30 15 14.55 12.5 1
40 30 44 33 1
29 84 33 58 4
9 39 41 115 2
75 47 37 69 4
46 26 58 25 3
73 48 27 59 3

Sample Output

240.610

1个回答

caozhy
caozhy   Ds   Rxr 2017.09.17 22:41
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
hdu 4856 Tunnels (BFS+状压)
题目链接 Problem Description Bob is travelling in Xi’an. He finds many secret tunnels beneath the city. In his eyes, the city is a grid. He can’t enter a grid with a barrier. In one minute, he can mov
HDU 4856 Tunnels(BFS+状压DP)
HDU 4856 Tunnels 题目链接 题意:给定一些管道,然后管道之间走是不用时间的,陆地上有障碍,陆地上走一步花费时间1,求遍历所有管道需要的最短时间,每个管道只能走一次 思路:先BFS预处理出两两管道的距离,然后状态压缩DP求解,dp[s][i]表示状态s,停在管道i时候的最小花费 代码: #include #include #include #inc
SSH-Tunnels
Skip navigation. SSH-TunnelsThe idea behind SSH tunnels is to encrypt otherwise unencrypted traffic. You can tunnel any TCP connection through SSH: VNC, POP3, …ConceptThe procedure is very
hdu 4856 Tunnels(bfs+状态压缩)
题目链接:hdu 4856 Tunnels 题目大意:给定一张图,图上有M个管道,管道给定入口和出口,单向,现在有人想要体验下这M个管道,问最短需要移动的距离,起点未定。 解题思路:首先用bfs处理出两两管道之间移动的距离,然后后用状态压缩求出最短代价,dp[i][j],i表示的已经走过的管道,j是当前所在的管道。 #include #include #include #inc
HDU-4856 Tunnels(BFS&&状压DP)
大致思路:先bfs预处理出任意两点的最短路,然后就转换为TSP问题,由于必经的隧道很小,所以可以用状压DP 设dp[i][j]表示当前i中二进制中为1的位已经走过,且最后一个走过的隧道为第j条隧道 【注意】必须把表示走过的某些隧道这个状态放在最外层,把隧道放在最内层,WA在这2.5h,还是不太熟悉状压DP 只有这样才能保证当前使用的状态是最优状态,否则就限定了部分遍历隧道的顺序 ①若未遍历的隧道在最外层,则限定了最后一个必定经过第m-1条隧道 ②若已遍历的隧道在最外层,则限定了倒数第二个必定经过第m-1条隧
算法竞赛入门经典学习笔记(三)——数组和字符串
数组只有在放在main函数外面时,才可以开得很大;放在main函数内时,数组稍大就会异常退出。 如果要从数组a复制k个元素到数组b,可以这样做:memcpy(b,a,sizeof(int) * k) 如果数组a和b都是浮点型的,复制时要写成memcpy(b,a,sizeof(double) * k) 使用memcpy函数要包含头文件string.h 如果需要把数组a全部复制到数组b中,可以写得简...
利用PuTTY的SSH Tunnels实现安全的代理
利用PuTTY的SSH Tunnels实现安全的代理 1 Comment五月 28, 2011 by 大漠标签:Putty使用 , SSH代理 安全外壳协议(Secure Shell Protocol / SSH)是一种在不安全网络上提供安全远程登录及其它安全网络服务的协议。最初是UNIX系统上的一个程序,后来又迅速扩展到其他操作平台。 常用的SSH工具有开
【安全牛学习笔记】补充Proxytunnel、stunnel4
stunnel4                                       无需修改源代码的情况下降TCP流量封装与SSL通道内 适用于本身不支持加密传输的应用                 支持openssl安全特性                            跨平台                                      
【HDU】4856 Tunnels BFS+状压DP
Tunnels Time Limit: 3000/1500 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 90    Accepted Submission(s): 28 Problem Description Bob is travelling in Xi’an
TCP tunnel (port forwarding) using Netcat
Here is how to establish a tunnel using netcat to a given host and port. netcat -L 127.0.0.1:22 -p 8080 -vvv Listen on port 8080 of the server, and when somebody tries to connect, establish a link