【CodeVS 2602 最短路径问题】

【CodeVS 2602 最短路径问题】

题目描述 Description 平面上有n个点(n<=100),每个点的坐标均在-10000~10000之间。其中的一些点之间有连线。若有连线,则表示可从一个点到达另一个点,即两点间有通路,通路的距离为两点间的直线距离。现在的任务是找出从一点到另一点之间的最短路径。 输入描述 Input Description 第一行为整数n。 第2行到第n+1...
【Minimum】

【Minimum】

【问题描述】 给出一幅由n个点m条边构成的无向带权图。 其中有些点是黑点,另外点是白点。 现在每个白点都要与它距离最近的黑点通过一些边连接(就是最短路)(如果有很多歌,可以选取其中任意一个。),我们想要使得花费的代价最小。请问这个最小代价是多少? 【输入格式】 第一行两个整数n,m; 第二行n个整数,0表示白点,1表示黑点 接下来m行,每行三个整数x y z...
【第二短路】

【第二短路】

题目描述 贝茜把家搬到了一个小农场,但她常常回到FJ的农场去拜访她的朋友。贝茜很喜欢路边的风景,不想那么快地结束她的旅途,于是她每次回农场,都会选择第二短的路径,而不象我们所习惯的那样,选择最短路。 贝茜所在的乡村有 R (1<=R<=100,000) 条双向道路,每条路都联结了所有的 N (1<=N<=5000) 个农场中的某两个...
【北京省选2012 冻结】

【北京省选2012 冻结】

题目背景 BJOI2012 第一轮 DAY2 T1 题目描述 我们考虑最简单的旅行问题吧:现在这个大陆上有 N 个城市,M 条双向的道路。城市编号为 1~N ,我们在 1 号城市,需要到 N号城市,怎样才能最快地到达呢? 这不就是最短路问题吗?我们都知道可以用 Dijkstra、Bellman-Ford、Floyd-Warshall 等算法来解决。 现...
【信号连接】

【信号连接】

题目描述 Nico 有一个排练室,她想把新买回来的 IMAX 银幕和放映机与远处的信号连接上,以便排练时可观看 lovelive 直播表演。 已知有 N 个信号发射仪,但其中只有 P 条线路能直接连接(Ai,Bi)(70%数据保证(A,B)只出现一次),且每条线路所花费的钱的就是该线路的长度 Li。保证源信号在 1 号点,排练室在 N 号点,且保证 1 和...