Aim Netbar(netbar.pas/c/cpp)

时间:2023-01-01 04:02:04


【问题背景】
金门县立中山国中以人数众多而闻名。三个年级共有10000 多人,学生多了附近的网吧也多。Mzoiers 都热衷于Dota,可学校的机子配置相当差(评测服务器除外),根本不能玩Dota,那就只有去网吧。星期天到星期五都是晚上10:20 才下晚自习,几乎没时间玩。然而星期六下午放假是绝好的时间,但是学校人多啊,一放学去网吧的人就开始狂奔,竞争之激烈,抢到机子的难度非常之大。往往在我们到达网吧之前都坐满了。学校到网吧的路是错综复杂的,以致于到一个自己想去的网吧都有非常多的路线可以选择,而路线的长度又不相同,这样就决定了要花费的时间,因此想要尽快到达,选择一条最佳的线路是很有必要的。

【问题描述】
为了简化问题,我们把学校与周边的网吧看做图中的顶点,学校与网吧,网吧与网吧之间的路线看做边,每个边都有一个权,表示我们走完这条路的时间,由于放学人流量大,如果反向走会有危险,因此这是一个有向图。
假设学校在S点,想要去的网吧在T点。你的任务就是选择一条最佳路线,使得从学校到目的地网吧的时间最短,你只需要输出最短到达时间即可。

【输入文件】
netbar.in *有M+2 行数据
第一行两个整数N,M,表示点数和边数。
然后M行每行3 个正整数(u,v,t),表示有一条可由u 到v耗时为t的边。
最后一行两个正整数S、T。

【输出文件】
netbar.out 中,只有一行,一个整数表示最短时间。如果S、T之间不存在通路则输出“No Solution!”(双引号不输出,“!”为西文标点)。

【输入样例】
4 4
1 2 3
2 4 10
1 3 5
3 4 5
1 4
【输出样例】
10


【数据规模】
对于30%的数据保证有1<N<=1000,1<=M<=1000;
对于全部的数据保证有1<N<=10000,1<=M<=100000。

这道题很明显就是用SPFA

A版:

Tot[i]表示第i 个结点相邻的结点数
F[i]表示结点1 到i 的最短距离
map[I,j]表示i 结点第j 个结点的序号
Que[i]当前队列

 

 1 Var
 2   i,n,m,l,r,q,s:longint;
 3   u,v,t:longint;
 4   Tot,f,Que:Array[0..10001] of longint;
 5   map,a:Array[0..10001,0..10001] of longint; //Vijos Error 255
 6 Begin
 7   Read(n,m);
 8   For i:=1 to m do
 9     Begin
10       Read(u,v);
11       Inc(Tot[u]);
12       Inc(Tot[v]);
13       Read(a[u,v]);
14       Map[u,Tot[u]]:=v;
15     End;
16   Read(s,t);
17   f[0]:=0;
18   l:=0;
19   r:=1;
20   Que[r]:=s;
21   While l<r Do
22     Begin
23       Inc(l);
24       q:=Que[l];
25       For i:=1 to Tot[q] Do
26         if (a[q,map[q,i]]+f[q]<f[map[q,i]]) Or (f[map[q,i]]=0) Then
27           Begin
28             Inc(r);
29             f[map[q,i]]:=a[q,map[q,i]]+f[q];
30             que[r]:=map[q,i];
31           End;
32     end;
33   If f[t]=0 Then Writeln('No Solution!') Else Writeln(f[t]);
34 End.

 

 

 

但是由于这个数据规模,我们只能有两种方法:1.链表 2.前向星

B版:(前向星优化)

Vis[i]该点是否已经访问
d[i]表示结点1 到i 的最短距离
Q[i]当前队列

f 前向星

 1 Var
 2   k,l,r:longint;
 3   u,v,t:array[0..100001] of longint;
 4   vis:array[0..20001] of boolean;
 5   q,d,f:array[0..20001] of longint;
 6   n,m,i,s,Tt:longint;
 7 Procedure qSort(l,r:longint);
 8   Var
 9     i,j,Tmp,Mid:longint;
10   Begin
11     i:=l;
12     j:=r;
13     Mid:=u[(l+r) Shr 1];
14     Repeat
15       While u[i]<Mid Do inc(i);
16       While Mid<u[j] Do Dec(j);
17       if i<=j then
18         Begin
19           Tmp:=u[i];
20           u[i]:=u[j];
21           u[j]:=Tmp;
22           Tmp:=v[i];
23           v[i]:=v[j];
24           v[j]:=Tmp;
25           Tmp:=t[i];
26           t[i]:=t[j];
27           t[j]:=Tmp;
28           inc(i);
29           Dec(j);
30         End;
31     Until i>j;
32     if i<r Then qSort(i,r);
33     if l<j Then qSort(l,j);
34   End;
35 Begin
36   Read(n,m);
37   For i:=1 to m do
38     Read(u[i],v[i],t[i]);
39   qSort(1,m);
40   For i:=1 to m do if f[u[i]]=0 Then f[u[i]]:=i;
41   f[n+1]:=m+1;
42   For i:=n Downto 0 do if f[i]=0 then f[i]:=f[i+1];
43   Read(s,Tt);
44   FillChar(Vis,SizeOf(Vis),False);
45   l:=0;
46   r:=1;
47   Q[r]:=s;
48   Vis[r]:=True;
49   Repeat
50     l:=l mod 10000+1; //循环队列(Ms是吧..)
51     k:=q[l];
52     For i:=f[k] to f[k+1]-1 do
53       Begin
54         if (d[k]+t[i]<d[v[i]]) Or (d[v[i]]=0) Then
55           Begin
56             d[v[i]]:=d[k]+t[i];
57             if Not Vis[v[i]] Then
58               Begin
59                 r:=r mod 10000+1;//循环队列(Ms是吧..)
60                 q[r]:=v[i];
61                 Vis[v[i]]:=True;
62               End;
63           End;
64       End;
65     Vis[k]:=False;
66   Until l=r;
67   if d[Tt]=0 Then Writeln('No Solution!') 
68   Else Writeln(D[Tt]);
69 End.

C版:数组模拟链表优化(本程序来自网络) http://blog.csdn.net/five213ddking/article/details/6633361

1 program NDK1068;  

2   

3 var  

4     n,m,st,ed,tot,head,tail:longint;  

5     map:array [-1..100001,1..3] of longint;  

6     b:array [-1..100001] of boolean;  

7     first,que,d:array [-1..100001] of longint;  

8   

9 procedure ycl(x,y,dis:longint);  

10 begin  

11     inc(tot);  

12     map[tot,1]:=y;  

13     map[tot,2]:=dis;  

14     map[tot,3]:=first[x];{相当于建立链表的过程,数组模拟指针}  

15     first[x]:=tot;  

16 end;  

17   

18 procedure init;  

19 var  

20     i,x,y,dis:longint;  

21 begin  

22     fillchar(d,sizeof(d),100);{初始化为大权值}  

23     fillchar(map,sizeof(map),0);  

24     fillchar(b,sizeof(b),false);  

25     fillchar(first,sizeof(first),0);  

26     tot:=0;  

27     readln(n,m);  

28     for i:=1 to m do  

29         begin  

30             readln(x,y,dis);  

31             ycl(x,y,dis);  

32         end;  

33     readln(st,ed);  

34 end;  

35   

36 procedure SPFA;  

37 var  

38     t:longint;  

39 begin  

40     head:=0;  

41     tail:=1;  

42     que[1]:=st;  

43     b[st]:=true;  

44     d[st]:=0;  

45     while head<tail do  

46         begin  

47             inc(head);  

48             t:=first[que[head]];{取出到队首的上一个指针指向的标识符}  

49             while t>0 do  

50                 begin  

51                     if d[que[head]]+map[t,2]<d[map[t,1]] then{如果当前队首的最优值+上一个标识符的权值<要到的那个点的最优值就更新那个点的最优值(类似于dijkstra的探测)}  

52                         begin  

53                             d[map[t,1]]:=d[que[head]]+map[t,2];  

54                             if not b[map[t,1]] then{判断状态是否已经存在,若不存在就更新状态入队}  

55                                 begin  

56                                     inc(tail);  

57                                     que[tail]:=map[t,1];{这里的队伍进入的是刚才探测到的那个点}  

58                                     b[map[t,1]]:=true;  

59                                 end;  

60                         end;  

61                     t:=map[t,3];{有点类似于递归的访问链表的下一层的操作}  

62                 end;  

63             b[que[head]]:=false;{刚才解释了,现在不解释}  

64         end;  

65     if d[ed]=d[0] then writeln('No Soulution!') else writeln(d[ed]);{这里是判断这个目标值刚才是否被更新过}  

66 end;  

67   

68 begin  

69     assign(input,'NDK1068.in'); reset(input);  

70     assign(output,'NDK1068.out'); rewrite(output);  

71       

72     init;  

73     SPFA;  

74       

75     close(input); close(output);  

76 end.  

D版:链表优化(本程序来自网络)http://hi.baidu.com/zhaiconglife/item/b7f6e11ee4c13b5c2a3e2221

program netbar;

const

maxn=10000000;

type

link=^tnode;

tnode=record

    data,w:longint;

    next:link;

end;

var

f:array[0..10000]of longint;

v:array[0..10000]of boolean;

d:array[0..10000]of link;

q:array[1..1000000]of longint;

n,m,st,ta:longint;

procedure insert(var h:link;x1,x2:longint);

var

p:link;

begin

new(p);

p^.data:=x1;

p^.w:=x2;

p^.next:=h;

h:=p;

end;

procedure readdata;

var

i,j,x,y,z:longint;

begin

fillchar(d,sizeof(d),0);

readln(n,m);

for i:=1 to m do

    begin

      readln(x,y,z);

      insert(d[x],y,z);

    end;

readln(st,ta);

end;

procedure main;

var

i,j,t,l,r,k:longint;

p:link;

begin

for i:=1 to n do

    f[i]:=maxn;

fillchar(v,sizeof(v),0);

l:=0;r:=1;

q[1]:=st;

v[st]:=true;

f[st]:=0;

repeat

     inc(l);

     k:=q[l];

     v[k]:=false;

     p:=d[k];

     while p<>nil do

       begin

         j:=p^.data;

         t:=p^.w;

         if f[j]>f[k]+t then

           begin

             f[j]:=f[k]+t;

              if not v[j] then

                 begin

                   inc(r);

                   q[r]:=j;

                   v[j]:=true;

                 end;

           end;

         p:=p^.next;

      end;

until l>=r;

if (f[ta]<>maxn) then writeln(f[ta])

else writeln('No Solution!');

end;

 

云盘下载(pdf):http://yunpan.cn/lk/sVksLEkffFdSc