《哈利·波特与魔法石》

大榕树 \ 信息学奥赛 \ 解题报告

《哈利·波特与魔法石》

原文链接：http://www.mydrs.org/program/list.asp?id=360
题目描述

　　在Super Samuel星球上，有n个城市，每两个城市都可以直接或间接到达，城市之间的路存在着不同的地形，通过每种地形所需时间是不同的，而且时间是固定的，但是路的长短却并不重要。如果路上有魔法石的话，则通过该路的时间将会减半。（如果城市1与城市2之间有路，我们认为城市1可以直接到城市2，城市2也可以直接到城市1）。现在求从a城市和 b城市最少需要花费多少时间。
算法分析

　　这是一道典型求最短路径的题目。
　　由于题目上说每两个城市之间的路最多只有一条，那么我们就可以用Road[i,j]来存放从城市i到城市j所需的时间。Road[i,j]如果为0，则代表从城市i不能直接到城市j 。而对于路a----b来说，我们可以知道通过路所在地形所花去的时间，如果这种地形有魔法石，则将时间减半。在所有城市之间的地图构造好之后，我们就可以利用Dijstra算法求出从城市a到城市b所需的最短时间了。
　　至此，本题已经得到圆满的解决
程序如下：

Const
　　InFile = 'AH02T7.in';
　　OutFile = 'AH02T7.out';
　　Limit = 102;
　　MaxLongint = 10000000;
　　cost : array[1..7] of longint
　　　　　= (2 , 6 , 4 , 8 , 6 , 10 , 14);
Type
　　Tmap = array[1..Limit , 1..Limit] of longint;
　　Tappeared = array[1..Limit] of boolean;
　　Tshortest = array[1..Limit] of longint;
Var
　　map : Tmap;
　　appeared : Tappeared;
　　shortest : Tshortest;
　　start ,
　　stop : longint;
procedure init; 　　　　　　　　　　　　　　　　　　// 初始化
type
　　Tdata = array[1..7] of longint;
var
　　data : Tdata;
　　i ,
　　p1 , p2 ,
　　k , total : longint;
begin
　　fillchar(appeared , sizeof(appeared) , 0);
　　for p1 := 1 to Limit do
　　　for p2 := 1 to Limit do
　　　　map[p1 , p2] := maxlongint;
　　assign(INPUT , InFile); ReSet(INPUT);
　　　for i := 1 to 7 do
　　　　begin
　　　　　　read(data[i]);
　　　　　　inc(data[i]);
　　　　end;
　　　read(start , stop , total);
　　　for i := 1 to total do
　　　　begin
　　　　　　　read(p1 , p2 , k);
　　　　　　　map[p1 , p2] := cost[k] div data[k];
　　　　　　　map[p2 , p1] := cost[k] div data[k];
　　　　　　　appeared[p1] := true;
　　　　　　　appeared[p2] := true;
　　　　end;
　　Close(INPUT);
end;
procedure work; {Dijkstra}　　　　　　　　　　　// 求从a到b的最短路径
type
　　Tvisited = array[1..Limit] of boolean;
var
　　visited : Tvisited;
　　i , min : longint;
begin
　　fillchar(visited , sizeof(visited) , 0);
　　for i := 1 to Limit do
　　　shortest[i] := map[start , i];
　　shortest[start] := 0;
　　while not visited[stop] do
　　　begin
　　　　　min := 0;
　　　　　for i := 1 to Limit do
　　　　　　if appeared[i] and not visited[i] then
　　　　　　　if (min = 0) or (shortest[min] > shortest[i]) then
　　　　　　　　min := i;
　　　　　visited[min] := true;
　　　　　for i := 1 to Limit do
　　　　　　if appeared[i] and not visited[i] then
　　　　　　　if shortest[min] + map[min , i] < shortest[i] then
　　　　　　　　shortest[i] := shortest[min] + map[min , i];
　　　end;
end;
procedure out;　　　　　　　　　　　　　　　　　　　　// 输出
begin
　　assign(OUTPUT , OutFile); ReWrite(OUTPUT);
　　　writeln(shortest[stop]);
　　Close(OUTPUT);
end;
Begin
　　init;
　　work;
　　out;
End.

作者：
来源：曙光
时间：2002-05-17

上一篇：Sgoi12之《网络传输》
下一篇：《Kitty猫基因突变》