这个旅行商的问题困扰了很久了,用邻接表怎么实现的?采用C语言

Problem Description
Long before the days of international trade treaties, a salesman would need to pay taxes at every border crossed. So your task is to find the minimum number of borders that need to be crossed when traveling between two countries. We model the surface of Earth as a set of polygons in three dimensions forming a closed convex 3D shape, where each polygon corresponds to one country. You are not allowed to cross at points where more than two countries meet.

Input
Each test case consists of a line containing c, the number of countries (4 ≤ c ≤ 6000), followed by c lines containing the integers n x1 y1 z1 … xn yn zn, describing (in order) the n corners of a closed polygon (3 ≤ n ≤ 20). Then follows a line with one integer m (0 < m ≤ 50), and then m lines with queries ca cb, where ca and cb are country numbers (starting with 1). No point will be on the line between two connected points, and -106 ≤ x, y, z ≤ 106 for all points. No two non-adjacent edges of a country share a common point. The input is terminated by a case where c = 0, which should not be processed.

Output
For each query, output the number of borders you must cross to go from ca to cb.

Sample Input
6
4 0 0 0 0 0 1 0 1 1 0 1 0
4 1 0 0 1 0 1 1 1 1 1 1 0
4 0 0 0 1 0 0 1 0 1 0 0 1
4 0 1 0 1 1 0 1 1 1 0 1 1
4 0 0 0 0 1 0 1 1 0 1 0 0
4 0 0 1 0 1 1 1 1 1 1 0 1
2
1 2
1 3
0

Sample Output
2
1

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问

相似问题

0
一个有关安于邻接矩阵的问题,是如何利用C语言编程实现的呢
0
查找最近的车站的一个算法问题,采用邻接矩阵的方式的表述,怎么计算的,运用C语言的相关知识
0
用邻接表实现距离数组的存储的计算,用C语言的程序编写的方法如何解决
1
用数组表示法(邻接矩阵)和邻接表两种存储结构分别表示下面的无向图。
2
数据结构图(用C语言)当中为什么邻接表用结构体变量报错,用邻接矩阵不报错?
1
请教数据结构#邻接链表表示图?
1
有向图任意两顶点之间存在的双边,则删除shuang bi an
1
邻接表双向BFS算法数组越界问题
1
编程实现有向图的深度和广度优先遍历
0
用邻接矩阵创建有向网,求最小生成树,最短路径(c语言)。
1
求教大佬们,这个“读取位置 0xCCCCCCCC 时发生访问冲突。”的异常该如何解决?
0
CCPC2019-秦皇岛F HDU-6736为什么这个题目把前向星换成邻接表就能AC啊?
0
在Windows7 64位+VS2015上运行求解AOE网关键路径的算法,邻接表表示的AOE网提示网中有回路,邻接矩阵表示的AOE网显示正确的信息?使用的算法是一样的,两种方法的相关类的接口函数也一致,为什么会出现这种问题?
0
floyd算法求任意两点最短路径,为什么输出的邻接矩阵总不正确
0
利用普利姆算法和克鲁斯卡尔算法实现最小生成树问题C语言或者C++语言实现
1
c语言实现的套汇问题 钱的种类多了就就不行了
1
局部聚类系数求法-用java 编程,图用邻接矩阵表示
2
请问有没有一种 O(V+E)的算法可以判断给定的一个图的邻接链表是否存在任何平行边?(判断这个邻接链表的图是否属于多重图)
2
设计一种O(V+E)的算法来将给定的一个图的邻接链表中包含的顶点按由小到大的顺序排列。