Question

一道c语言的题目

重庆城里有n个车站，m条双向公路连接其中的某些车站。每两个车站最多用一条公路连接，从任何一个车站出发都可以经过一条或者多条公路到达其他车站，但不同的路径需要花费的时间可能不同。在一条路径上花费的时间等于路径上所有公路需要的时间之和。
佳佳的家在车站1，他有五个亲戚，分别住在车站a,b,c,d,e。过年了，他需要从自己的家出发，拜访每个亲戚（顺序任意），给他们送去节日的祝福。怎样走，才需要最少的时间？
输入
　第一行：n(n<=50,000),m(m<=100,000)为车站数目和公路的数目。
第二行：a,b,c,d,e，为五个亲戚所在车站编号（1<a,b,c,d,e<=n）。
以下m行，每行三个整数x,y,t（1<=x,y<=n,1<=t<=100）,为公路连接的两个车站编号和时间.
输出
　仅一行，包含一个整数T，为最少的总时间
样例输入
6 6
2 3 4 5 6
1 2 8
2 3 3
3 4 4
4 5 5
5 6 2
1 6 7

样例输出
21

Answer 1

type ss=record
a,b,c,next:longint;
end;
var n,m,i,j,rp,k,x,y,tot,z:longint;
im:boolean;
map:array[0..200001] of ss;
q:array[0..100001] of longint;
s,a:array[0..50001] of longint;
f:array[0..50001] of boolean;
d:array[0..5] of longint;
l:array[0..5,0..5] of longint;
dp:array[0..5,0..63] of longint;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
procedure swap(var a,b:longint);
var t:longint;
begin
t:=a; a:=b; b:=t;
end;
procedure jia(x,y,z:longint);
begin
inc(tot);
map[tot].a:=x;
map[tot].b:=y;
map[tot].c:=z;
map[tot].next:=a[x];
a[x]:=tot;
end;
function spfa(x,y:longint):longint;
var h,t,temp,i,j,p,d,hh,tt:longint;
begin
fillchar(f,sizeof(f),false);
fillchar(s,sizeof(s),$7f);
s[x]:=0;
h:=1;
hh:=1;
tt:=1;
t:=1;
f[x]:=true;
q[1]:=x;
repeat
temp:=q[h];
f[q[h]]:=false;
inc(h);
if h>100000 then h:=1;
inc(hh);
p:=a[temp];
while p<>-1 do
begin
if s[map[p].b]>s[temp]+map[p].c then
begin
s[map[p].b]:=s[temp]+map[p].c;
if not(f[map[p].b]) then
begin
if s[map[p].b]<=s[q[h]] then
begin
dec(h);
dec(hh);
if h<1 then h:=100000;
q[h]:=map[p].b;
end
else
begin
inc(t);
inc(tt);
if t>100000 then t:=1;
q[t]:=map[p].b;
end;
f[map[p].b]:=true;
end;
end;
p:=map[p].next;
end;
until hh>tt;
exit(s[y]);
end;
begin
readln(n,m);
for i:=1 to 5 do
read(d[i]);
d[0]:=1;
fillchar(a,sizeof(a),255);
for i:=1 to m do
begin
read(x,y,z);
jia(x,y,z);
jia(y,x,z);
end;
rp:=maxlongint;
for i:=0 to 4 do
for j:=i+1 to 5 do
begin
l[i,j]:=spfa(d[i],d[j]);
l[j,i]:=l[i,j];
end;
fillchar(dp,sizeof(dp),$7f);
dp[0,1]:=0;
repeat
im:=false;
for i:=1 to 5 do
for j:=0 to 5 do
if i<>j then
for k:=((1 shl i)+(1 shl j)) to 63 do
if dp[i,k]>dp[j,k-1 shl i]+l[j,i] then
begin
dp[i,k]:=dp[j,k-1 shl i]+l[j,i];
im:=true;
end;
until not(im);
for i:=1 to 5 do
rp:=min(rp,dp[i,63]);
writeln(rp);
end.

追问

for k:=((1 shl i)+(1 shl j)) to 63 do如何理解

Answer 2

这是C语言中的最短路径问题，有具体的算法可以参考
网址：http://baike.baidu.com/link?url=UCTL-G7RD-AZEoyBfD5u6zEYdlBxSfdzkOSRzQlO_MlXlCozwhBFwpMHyFbJniKa

追问

这个我知道

追答

。。知道 那你问什么。。让人帮你写？

Answer 3

判断有几条路，选择最短的，继续，直至六个点已全部访问

追问

我知道，但是具体写起来有问题