题目描述
在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);
inc(data);
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 := map[start , i];
shortest[start] := 0;
while not visited[stop] do
begin
min := 0;
for i := 1 to Limit do
if appeared and not visited then
if (min = 0) or (shortest[min] > shortest) then
min := i;
visited[min] := true;
for i := 1 to Limit do
if appeared and not visited then
if shortest[min] + map[min , i] < shortest then
shortest := 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.
