POJ 最短路问题题号汇总

求最短路基本的算法:

1>Dijkstra算法
2>Bellman-Ford算法
3>Floyd算法
4>Floyd-Warshall算法
5>Johnson算法
6>A*算法

题目:

1.poj1062
昂贵的聘礼
(中等)

    此题是个经典题目;用Dijkstra即可;但是其中的等级处理需要一定的技巧;

   要理解好那个等级制度;这个处理好,基本就是裸体Dijkstra;

poj1125
Stockbroker Grapevine
(基本)

   这个是简单Floyd,需要求出的是每对顶点之间的最短路径;

   然后找到那个所需时间最小的那个人中的所需时间;

3,poj
1502 MPI Maelstrom
(基本)【已经解决之,Dijkstra直接水之】

    这题是邻接矩阵的Dijkstra就可以解决的;

    直接水之;

4,poj
1511 Invitation Cards
(中等)

    这个时间上有点卡了。Dijkstra,bellman可能会TLE;用SPFA+邻接表可以过的;

    有个地方注意一下就好了,每个志愿者回来的时候的最短路径;将原图的每条边反向一下,对端点1再来

    SPFA就可以来;

    正向图的结果+逆向图的结果就是所求;

5,poj
1724 ROADS
(中等偏上)

    题意是在一定的coins的限制下的最短路径;可以用Dijkstra的变形;

    用邻接边来存储边;

    松弛过程中用优先队列(边的长度短的优先)来存储边,将符合条件(coins限制)的边都加入优先队列;

    直到找到延伸到最后一个顶点即可终止循环; 因为最先到达的一定是最短路径,在coins的限制条件下;

6,poj1797
Heavy Transportation
(中等)

    从端点1到端点n的能够通过的最大载重;

    可以用Dijkstra变形一下,在松弛时要改变一下松弛的条件;

    另外results数组中存储的不是每个点到1的最短距离,而是能够通过的最大载重;

    这题的输出让我灰常无语,以后输出要看清啦。。

7,poj
1860   currency exchange
(基本)

    这个是bellman_ford的经典应用;

    一个套汇问题,就是通过一系列的货币交换能够到达价值增加的目的;

    就是类似判断有没有负权回路;

    类似与poj2240,poj3259;

8,poj2240
Arbitrage
(基本)http://hi.baidu.com/lewutian

    这个是poj1860的简化版本;就不多说了。。

    直接bellman水之;

9,poj
2253 Frogger
(中等)

    和poj1797类似,所求的正好相反,也是Dijkstra的变形经典应用;

    改变一下松弛时的条件;

10,poj
2387   Till the Cows come home
(基本)

     注意其中可能有重边;然后就是赤裸的Dijkstra;

11,poj
2502    Subway
(基本)

    可以用Floyd来搞定,关键是哪个边的存储,存储后就是灰常简单的Floyd了;

12,poj
3013 Big Christmas Tree
(中等)

    这个要有个重要的转化;首先price of an edge will be (sum of weights of all descendant nodes) × (unit price of the edge).

    这句指出每条边的代价为该边所有子孙节点权值之和乘以该边的权值。

    换个角度就是每个节点的代价为该节点到根节点的所有边的权值乘以该节点的权值。

   其实就是求从端点1到每个点的最短路径*改点的权值,,然后之和;

    貌似,数据有点大,用SPFA吧。。

13,poj
3037 Skiing
(中等)

    这个题有点意思;刚开始想用bfs;

    后来发现对于每个点从该点出发的速度是恒定的,例如从a->b->c;则c出发的速度就是V*2^(A-B)*2^(B-C)=V*2^(A-C);

    所以直接求最短路径就可以了,边也知道了。用spfa。。

14,poj
3159 Candies
(中等)

    我靠,这个题时间卡的好紧啊!我的spfa是1400ms,时限是1500ms,汗一下;

    题意有点难理解,想明白了,其实就是求一个从1->n的最短路径;

15,poj
3259 Wormholes
(简单)

    这个题和poj1860,poj3259基本一样;

    求负权回路是否存在;用bellman直接水之;

16,poj
3268 Silver Cow Party
(基本)

    Dijkstra可以直接过的。。只不过求的有变化;

17,poj
3377Ferry Lanes
(中等)

    这题可以用最短路做的;但是我看和导论那个流水线那个dp例子灰常像;

    于是就dp过了,其中有个地方需要注意,dp的话,就是可以需要检查两端的情况;

    有兴趣的可以两种都试试;

18,poj
3615 Cow Hurdles
(中等)

    Floyd求出每个端点之间的路径中最大高度是最小的那个最大高度;

    要改变一下松弛的条件;  

19,poj
3660 Cow Contest
(中等)

    这个题有点topsort的意思,其实可以用Floyd来做,而且用的很巧妙;

    邻接矩阵中用0,1,2来分别存储关系不能确定,在之前,在之后;

    然后判断每个点哪行,如果除了对角线处,没有0出现的话,那么它的位置就可以确定了。。

转自:http://blog.sina.com.cn/s/blog_6f6e97490100tlmj.html

时间: 2024-10-29 04:43:48

POJ 最短路问题题号汇总的相关文章

c++ 编程 poj-poj上总是答案错误题号是1002 487-3279

问题描述 poj上总是答案错误题号是1002 487-3279 错误的地方很有可能出现在我标记的地方(见程序),但是我本人找不出来,求帮忙!求指教输出就是不对不知道什么原因.#include#include#include#includeusing namespace std;int LetterToInt[26]={}; int DiaNum[100000];int Numcounter[100000]; int main(){ int ijn; while(scanf(""%d&q

现用C#做一个调查问卷,需要提交时向数据库中查数据,只需要插入题号与对应选项,请问该如何插入

问题描述 现用C#做一个调查问卷aspx页面的,需要提交时向数据库中查数据,但是题跟选项有些多(大概70多道题,每道大概5.6个选项),只需要插入题号与对应选项,请问该如何插入?有没有什么简便方法? 解决方案 解决方案二:问卷调查虽然不记名,但也是需要记录性别.年龄.文化程度.地域.工作等信息的,不然时候分析起来不方便当然这些本就可以包含在题目中所以数据库中是以问卷为单位保存的:一张问卷一条记录也就是一个题目一个字段,如果是多选题,可用逗号连接各选项为一个串(分析时再拆开)程序只是拼装一个SQL

网络考试时点击右侧选题面板上的题号,就可以快速定位到该题,而且答过的题题号变色显示。

问题描述 网络考试时点击右侧选题面板上的题号,就可以快速定位到该题,而且答过的题题号变色显示.类似效果http://m.baidu.com/tc?from=openapp_bdimage_mobile&srd=1&dict=20&src=http%3A%2F%2Fwww.xymzxx.com%2Fxwgk%2FShowArticle.asp%3FArticleID%3D248

用repeater绑定并显示选择题,想通过在页面上设置选题面板实现点击题号页面自动定位该试题,做完的题,题号自动变色显示,怎么实现?

问题描述 绑定显示试题已经实现了,就是选题面板功能不知道该怎么做,请教大家! 解决方案 解决方案二:如果与数据库交互的话,你可以结合ajax实现你的效果.

JavaScript判断数字是否为质数的方法汇总_javascript技巧

前言 今天看到一个题目,让判断一个数字是否为质数.看上去好像不难.因此,我决定实现一下. DOM结构 <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>计算500以内的质数并输出</title> <meta name="viewport" content="width=d

php将数组存储为文本文件方法汇总_php技巧

php 缓存数组形式的变量,实际上就是将 php 将数组写入到一个文本文件或者后缀名为 .php 存储起来,使用的时候直接调用这个文件.那么如何使用 php 将数组保存为文本格式的文件呢?下面分享三种方法实现将 php 数组写入到文件以缓存数组.(1)利用serialize 将数组序列化存储为文本文件,调用时候再使用unserialize 还原 <?php $file='./cache/phone.php'; $array=array('color'=> array('blue','red',

PHP文件上传问题汇总(文件大小检测、大文件上传处理)_php技巧

由于涉及到本地和服务器两方面的安全问题,所以基于input type="file"形式的页面文件上传一直处于一个很尴尬的位置.一方面,用户不希望隐私泄露,所以浏览器无法对用户在上传时选择的文件做有效的判 断.另一方面,为了服务器端的安全,减轻传输负担,系统又希望能在用户开始上传之前就将非法的文件拒之门外. 一来一去,基于原始input方式的上传,成为网络存储网站避之唯恐不及的遗留性问题,也造就了现在千奇百怪的插件.上传客户端. input方式的上传就如此之差么?当然不是.上传文件不大的

jQuery操作Table技巧大汇总_jquery

本文汇总了jQuery操作Table的技巧.分享给大家供大家参考,具体如下: 1.鼠标移动行变色 方法一:jQuery中的hover(fun(),fun())方法,参数一:第一个方法是添加样式功能,参数二:第二个方法是取消样式功能 $("#table1 tr").hover(function(){ $(this).children("td").addClass("hover") },function(){ $(this).children(&qu

PHP获取当前文件的父目录方法汇总_php技巧

方法一:先获得当前文件所在文件夹的长度,然后用substr来截取掉该长度: 复制代码 代码如下:  $dirName = str_replace("\\", "/", dirname(__FILE__));  $dirNameLength = strlen($dirName);  $currentDirNameLength = $dirNameLength - strrpos($dirName,"/"); //获得当前文件所在文件夹的长度!  $