【问题背景】
金门县立中山国中以人数众多而闻名。三个年级共有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