笑笑最短路径与标号法
最短路径与标号法
前面我们学习过动态规划的应用，图中没明显阶段求最短路径的问题属于无明显阶段的动态规划，通常用标号法求解，求最短路径问题是信息学奥赛中很重要的一类问题，许多问题都可转化为求图的最短路径来来解，图的最短路径在图论中有经典的算法，本章介绍求图的最短路径的dijkstra算法、Floyed算法，以及标号法。
一、最短路径的算法
1、单源点最短路径(dijkstra算法)
给定一个带权有向图G=(V，E)，其中每条边的权是一个非负实数，另外，还给定V中的一个顶点，称为源点。求从源点到所有其他各顶点的最短路径长度。这个问题称为单源最短路径问题。求单源最短路径可用dijkstra算法求解。
(dijkstra算法)算法思想:
设源点为x0，dist[i]表示顶点i到源点x0的最短路径长度，map[i,j]表示图中顶点i到顶点j的长度，用数组mark对所有的顶点作标记，已求出源点到达该点J的最短路径的点J记为mark[j]=true,否则标记为false。初始时，对源点作标记，然后从未作标记的点中找出到源点路径长度最短的顶点minj，对该顶点作标记，并对其它未作标记的点K作判断:if dist[minj]+map[minj,k]
0) then
begin
temp:=dist[minj]+map[minj,j];
if temp0) then
begin
temp:=dist[minj]+map[minj,j];
if tempfirst then writeln(fout,i,’ ‘,dist[i]);
close(fout);
end;
2、所有顶点对之间的最短路径 Floyed算法
设图G=(V，E)，顶点I到顶点J的权为cost[I,j], 顶点I到 顶点J 的最短路径长度为A[I，J]，路径为P[I，J]。
Floyed算法 算法思想:
从任意顶点VI到VJ的路径上，每次增加一个顶点VK(K=1，2，„, N)，然后，比较增加VK后的路径是否比原来的路径短，取其中短者作为从VI到,,的当前最短路径。当,从取值,到取值,， 经过,次这样的比较后，最终求得的就是任意两顶点,，和,,间的最短路径。
算法过程:
const n=50;
type
pathdata=array[1..n,1..n] of 0..n; mapdata=array[1..n,1..n] of integer; var
p: pathdata; a:mapdata;
procedure path(var p:pathdata; I,j:integer);
var k:integer;
begin
k:=p[I,j];
if k<>0 then
begin
path(p,I,k);
writeln(k);
path(p,k,j);
end;
end;
procedure floyed(var a,cost:mapdata; var p:pathdata);
var I,j,k:integer
begin
for I:=1 to n do
for j:=1 to n do
begin
a[I,j]:=cost[I,j]; path[I,j]:=0;
end;
for k:=1 to n do
for I:=1 to n do
for j:=1 to n do
if a[I,k]+a[k,j]ma then ma:=j;
if k>ma then ma:=k;
se:=se+[j]+[k];
end;
close(f);
end;
procedure main;
var i,j,k:integer;
begin
for i:=1 to ma do
for j:=1 to ma do
if(i in se)and(i<>j)and(j in se)then
begin
for k:=1 to ma do
if(k<>i)and(k<>j)and(map[i,k]>0)and(map[k,j]>0)and(map[i,k]+map[k,j]0) then
begin
sum[j]:=sum[temp]+map[temp,j];
close:=close+1;
按代价由小到大将结点J插入队列;
fa[j]:=open;
end;
open:=open+1;
until open>close
例3:Car的旅行路线
问题描述
又到暑假了，住在城市A的Car想和朋友一起去城市B旅游。她知道每个城市都有四个飞机场，分别位于一个矩形的四个顶点上，同一个城市中两个机场之间有一条笔直的高速铁路，第I个城市中高速铁路了的单位里程价格为Ti，任意两个不同城市的机场
之间均有航线，所有航线单位里程的价格均为t。
图例
机场
高速铁路
飞机航线
注意:图中并没有
标出所有的铁路与航线。
那么Car应如何安排到城市B的路线才能尽可能的节省花费呢?她发现这并不是一个简单的问题，于是她来向你请教。
任务
找出一条从城市A到B的旅游路线，出发和到达城市中的机场可以任意选取，要求总的花费最少。
输入文件:键盘输入文件名
输 出:到屏幕(输出最小费用，小数点后保留2位。)
输入格式
第一行为一个正整数n(0<=n<=10)，表示有n组测试数据。
每组的第一行有四个正整数s，t，A，B。
S(0Tmp_Value) or (Line[i].Son=0));
if Line[i].Son=0 then begin
Line[i].Son:=Tail;
Line[Tail].Father:=i;
Line[Tail].Son:=0;
end else begin
Line[Tail].Fahter:=Line[i].Father;
Line[Tail].Son:=i;
Line[i].Father:=Tail;
end;
end else begin
end;
end;
end;
until Fintout;
end;
procedure Made_The_4th_Point; var
i,j,P1,P2,P3:integer;
Max:real;
begin
Max:=0;
for i:=(d-1)*4+1 to (d-1)*4+2 do
for j:=i+1 to (d-1)*4+3 do
if Get_Length(i,j)>Max then begin
Max:=Get_Length(i,j);
P1:=i;
P2:=j;
end;
P3:=(d-1)*4*3+6-P1-P2;
Airport[d*4].x:=Airport[P1].x+Airport[P2].x-Airport[p3].x;
Airport[d*4].y:=Airport[P1].y+Airport[P2].y-Airport[p3].y;
end;
begin
assign(RF,ReadFile);
reset(RF);
readln(RF,n);
for c:=1 to n do begin
readln(RF,s,t,A,B);
for d:=1 to s do begin
for e:=1 to 3 do read(RF,Airport[(d-1)*4+e].x,Airport[(d-1)*4+e].y);
Made_The_4th_Point;
read(RF,Railway[c]);
end;
Head:=0;
Tail:=4;
for d:=1 to 4 do begin
Line[d].Father:=0;
Line[d].Son:=d+1;
Line[d].Airport:=A*4-4+d;
Line[d].Value:=0;
end;
Line[4].Son:=0;
Main;
end;
close(RF);
end.
三、练习
1、最佳路线
问题描述
塞内加尔是非洲的一个小国家，你也许很难在世界地图上找到它，甚至你有可能从未听说过它--它实在是个太小、太贫穷的国家了。可是，就是这个人口不足900万、全
国仅有2个标准足球场地的小国，在2002韩日世界杯的非洲区预选赛中脱颖而出，取得了世界杯决赛圈的入场券(幸好，去年中国队也进入了世界杯决赛圈，不然可就丢脸了)。
在塞内加尔全国球迷欣喜若狂，世界足球行家大跌眼镜的同时，塞内加尔足协却发现自己面临着一个颇为尴尬的问题--说起来令人不可思议，由于打非洲区预选赛时四处征战，加上足协经营不力，现在足协的预算以几近赤字--也就是说，塞内加尔足协支付不起从本国乘飞机到达韩国参加世界杯的费用～经过三思，塞内加尔足协向非洲足联递交了一份《关于减免球队旅行费用》的申请;可是--众所周知的，非洲足联也是惨淡经营，幸好非洲足联秘
书
关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf
长神通广大，弄来了M张优惠乘机券:每张优惠券可以作用于一条航线，使全队通过此航线的费用减半;多张优惠券用于同一条线路，其效果叠加--即在一条航线上用两张优惠券，其费用降为原费用的1/4，依此类推。 【问题】
塞内加尔足球队要从塞内加尔国家机场出发，途经一些中转机场，最后要到达韩国釜山机场。为了合理地分配各张优惠券，使得所需费用最少，塞内加尔足协找到了你，请你编程解决这个问题。
【输入】
第1行有两个数N、M(0"连接(参见样例输出);
输入数据保证从塞内加尔机场可达釜山机场。
【样例输入】
5 2
0 0 80 96 0
70 0 72 54 0
18 0 0 99 82
72 18 71 0 0
69 0 0 70 0
【样例输出】
81.00
1->3->5
2、邀请卡分发
AMS公司决定在元旦之夜举办一个盛大展览会，将广泛邀请各方人士参加。现在公司决定在该城市中的每个汽车站派一名员工向过往的行人分发邀请卡。
但是，该城市的交通系统非常特别，每条公共汽车线路都是单向的，且只包含两个车站，即起点站与终点站，汽车从起点到终点站后空车返回。
假设AMS公司位于1号车站，每天早上，这些员工从公司出发，分别到达各自的岗位进行邀请卡的分发，晚上再回到公司。
请你帮AMS公司编一个程序，计算出每天要为这些分发邀请卡的员工付的交通费最少为多少,
输入格式:
输入文件的第一行包含两个整数P和Q (1<=P,Q<=50000)。P为车站总数(包含AMS公司)，Q为公共汽车线路数目。接下来有Q行，每行表示一条线路，包含三个数:起点，终点和车费。所有线路上的车费是正整数，且总和不超过1000000000。并假设任何两个车站之间都可到达。
输出格式:
输出文件仅有一行为公司花在分发邀请卡员工交通上的最少费用。 输入输出样例
样例1:
输入
2 2
1 2 13
2 1 33
输出
46
样例2:
输入
4 6
1 2 10
2 1 60
1 3 20
3 4 10
2 4 5
4 1 50
输出
210
3、恶魔城
问题描述:
上帝需要创造一位战士去消灭撒旦，这位战士必须要穿过恶魔城才能与撒旦决斗。恶魔城内有M条连接N个路口(从1到N编号)的街道，每一条街道都是单向的(也就是说你不能逆着该街道指定的方向走)，并且在城内无论怎么走都不可能走回原来走过的地方。开始的时候，战士的生命力(HP)为INITHP、站在,号路口，而撒旦在第N号路口等待着他。每一条街道上都有许多魔鬼，但是也有一些街道已经被上帝派去的天使占领了。当战士经过连接i号向j号路口的街道时，如果占领该街道的是恶魔，那么他的HP先加倍然后减少L[i,j]，我们记为A[i,j]=-L[i,j];如果占领该街道的是天使，那么他的HP就会先加倍然后增加L[i,j]，我们记为A[i,j]=+L[i,j];如果该街道不存在，那么A[i,j]=0。如果某一时刻战士的HP<=0，那么他会死亡。因为这个战士将非常无敌，当他见到撒旦的时候只要还活着，就能一口气把撒旦消灭，所以上帝不希望让他的INITHP过高。
任务:
给定N，A[1..N,1..N]，求最小的INITHP，使这个战士能够活着见到撒旦。 输入格式:
从文件SATANIC.DAT读入数据，文件第一行有一个正整数N(3 ? N ? 100)，下面跟着的第i行第j个数为A[i,j](绝对值不超过10000的整数。 )
输出格式:
输出所求最小的INITHP。
样例
SATANIC.DAT SATANIC.OUT
4 4
0 -4 0 –10
0 0 +3 0
0 0 0 –14
0 0 0 0
1、一日，煮鸡蛋碰上了煎鸡蛋，煎鸡蛋说:“蛋哥啊~做蛋不要太滑了。” 然后煮鸡蛋说:“蛋弟呀，做蛋不能太油了～”
煎鸡蛋。。。。。。
2、紫薇:尔康，你幸福吗,
尔康:你忘了吗，我一直姓福。
3、身体有点不舒服，去看医生。
“哦，不舒服啊,来，咳嗽一下我听听„„好，再咳两声„„嗯，你这个情况啊我清楚了:你呢，是咳嗽。”
4、“有女朋友吗,”
“有了。”
“有钱人啊你。”
“......”
5、老婆:“今天情人节，你是要爱惜钱包呢,还是保重身体,” 1、有三个人去看戏，一个是聋子，一个是瞎子，一个是歪脖子。 看完了戏，演员问他们:“戏怎么样,”
聋子说:“还行，就是没有声音。”
瞎子说:“烂透了，根本就没人演～”
歪脖子说:“挺不错的，就是戏台有点歪。”
2、三毛去发型屋做发型，对发型师说:给我编个麻花辫。发型师不小心弄掉了三毛的一根头发。
三毛叹口气说:那来个中分好拉。
可是发型师不小心又弄掉了根。
三毛一看火了:你丫的想让我披头散啊,～
3、乡间有个小偷，夜里来到老头家窥探，正好被从外面回来的老头看见。 小偷慌忙夺路而逃，情急之下连从别人家偷来的羊皮袄也顾不得了。 老头从地上拾起小偷丢下的羊皮袄，穿在身上一试很合身，心里非常高兴。 由于这次白白捡了个大便宜，以后他每次夜里回到家时，见到门庭平安无事，心里就很失望，总是皱紧眉头，不住地念叨着:“今夜怎么就没来小偷呢,” 4、话说有一个美女深夜被打劫，劫匪“把身上值钱的东西都拿出来～”，美女遂从之，劫匪拿了东西又仔细盯了美女一会“把衣服全脱了～”
美女心想终究还是逃不过，遂从之。
男子认真看她脱完后“算你老实，没藏东西”于是掉头就走了。。。 、有一个人患有高度近视，半尺之外，几乎什么都看不清。 5
一天晚上，他捡到一个爆竹，便靠近灯火辨认，不料触火而响。
旁边有一个聋人，见此，拍着他的背问:“你刚才捡到了什么东西,怎么一到手就飞散了,”
1、一天爸爸给儿子讲故事。
爸爸:“在春秋时代„”
儿子:“说清楚是春还是秋,”
爸爸:“有一个诸侯„”
儿子:“到底是猪还是猴啊,”
爸爸:“„”
2、儿子今年三岁半，最近爱上角色扮演的游戏。
儿子说:“爸爸我是饺子，你把我吃掉吧～”
于是我老公就非常投入的在儿子肚子上乱拱。嘴里还吧嗒吧嗒发出声音逗得孩子咯咯直笑。 儿子边笑边问:“爸爸我好吃不,”
老公说:“好吃呀～比妈妈包的饺子好吃多了。哎呀，宝贝你是什么馅的饺子呀,” 想去便便的儿子很认真地说:“爸爸，我是屎馅的～”
3、一个人的儿子被蚊子叮了，他给儿子风油精并对儿子说:“风油精中含有一种东西，蚊子闻了就害怕，就不会来咬你了。”
儿子说:“要是它捏着鼻子回来怎么办,”
4、今天朋友发给我一张她8个多月大女儿的照片，照片中小宝宝手拿着吃了一半的香蕉，撇着嘴在哭。
我很惊奇的问朋友，“她会吃香蕉呀”,
朋友回答:“是啊。”。
我又问:“那她为什么哭得这么伤心”,
朋友的回答把我笑喷了:“穿得太厚了，她胳膊又短，吃了一半够不着了”。
1、学校辩论赛上。
正方辩题:人为他人而活。
反方辩题:人为自己而活。
反方提问正方:“对方辩友既然是为了他人而活，那你能给我买个肉夹馍么,” 正方:“„„能。”
反方:“那你别比赛了，现在就去买吧。”
正方:“„„”
2、有一次四级考试我做监考，当时我在讲台上坐着，看到下面一名男生鬼鬼祟祟，一只手在上面写，一只手在下面动，嘴里还念念有词。
我心想这肯定是在作弊，于是走过去一看，TMD这哥们手里赫然拿着一串佛珠„„ 3、上课，哥们在手机上玩切水果，切切切。突然他把游戏暂停，因为手上有汗，在衣服上蹭来蹭去。 我就问:“你干嘛呢,”
他抬起头举着手，对我说:“磨刀～”
、上机课无聊我就玩游戏，玩模拟器版的1945(飞机游戏)，玩了一上午。 4
中午和一群同学去食堂打饭，边走边侃，我说:今天打一早上的飞机，手都打痛了～~ 招来一群人狂笑。。。
5、一次物理课，讲到安培定律。
老师问我们判断一个带电流导体在磁场中受力方向用左手还是用右手定则，有说用左手有说用右手的，久久没有确定的答案。。
无奈之下老师说道:“男左女右,”
1、儿子问:我数了好多遍，明明英语是28个字母，为啥说是26个呢。 爸爸疑问道:你现在数下给我看看,
他用手指数字母ABCD......到W就把“达、不、了”给算上了。
2、爸爸:“房间里好冷啊。”
儿子:“你可以站到墙角去。”
爸爸:“为什么啊„”
儿子:“因为墙角有90度。”
3、有个小孩了，考试只考了18分，然后他拿红笔添了一横，变成了78，然后又在7的上面多加了半圈，然后。。就变成了98。
后来卷子拿给他妈妈看，他妈妈说:这么明显的改动，你以为我会看不出来你其实考了78分吗,
4、小学历史课上，老师问同学道:“谁知道地球围着什么转呀。”
许多同学都举手了，老师叫小明回答，小明说:“地球围着太阳转。”老师又叫 几个同学回答，同学都和小明回答得一样。历史老师又问:“那你们谁知道最早提出地球
围着太阳转的人是谁。”
同学们齐声说到:“小明。”
浙公网安备 33021202002483