2292: 【POJ Challenge 】永远挑战
2292: 【POJ Challenge 】永远挑战
HansBug
发布于 2018-04-11 10:43:17
发布于 2018-04-11 10:43:17
2292: 【POJ Challenge 】永远挑战
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 553 Solved: 230
Description
lqp18_31和1tthinking经常出题来虐ftiasch。有一天, lqp18_31搞了一个有向图,每条边的长度都是1。 他想让ftiasch求出点1到点 N 的最短路。"水题啊。", ftiasch这么说道。
所以1tthinking把某些边的长度增加了1（也就是说，每条边的长度不是1就是2）。现在，可怜的ftiasch要向你求助了。
Input
第1行，两个整数 N (1 ≤ N ≤ 105) 和 M (1 ≤ M ≤ 106), 点和边的数量。
第2到 M + 1行: 三个整数 Ui, Vi, Wi (1 ≤ Wi ≤ 2), 从点 Ui 到 Vi 长度为 Wi 的边。
Output
一个整数，表示点1到点N的最短路。数据保证至少存在一条路径。
Sample Input
3 3 1 2 1 2 3 1 1 3 2
Sample Output
2
HINT
Source
题解：乍一看这不是明显的spfa嘛= =，不过要是那样子的话也太没意思了，于是想想别的办法——BFS，这里不是说了最多边权只有2嘛，所以将2的拆成两条边就好啦，然后水水哒BFS
以下是对比——spfa居然慢了这么多，汗QAQ
spfa代码（险些T掉有木有TT）：
1 /**************************************************************
2 Problem: 2292
3 User: HansBug
4 Language: Pascal
5 Result: Accepted
6 Time:9528 ms
7 Memory:6492 kb
8 ****************************************************************/
9
10 type
11 point=^node;
12 node=record
13 g,w:longint;
14 next:point;
15 end;
16 var
17 i,j,k,l,m,n,f,r:longint;
18 a:array[0..100005] of point;
19 c,g,d:array[0..100005] of longint;
20 p:point;
21 procedure add(x,y,z:longint);
22 var p:point;
23 begin
24 new(p);p^.g:=y;p^.w:=z;p^.next:=a[x];a[x]:=p;
25 end;
26 begin
27 readln(n,m);for i:=1 to n do a[i]:=nil;
28 for i:=1 to m do
29 begin
30 readln(j,k,l);
31 add(j,k,l);
32 end;
33 fillchar(c,sizeof(c),255);fillchar(g,sizeof(g),0);
34 c[1]:=0;f:=1;r:=2;g[1]:=1;d[1]:=1;
35 while f<>r do
36 begin
37 p:=a[d[f]];
38 while p<>nil do
39 begin
40 if (c[p^.g]=-1) or ((c[d[f]]+p^.w)<c[p^.g]) then
41 begin
42 c[p^.g]:=c[d[f]]+p^.w;
43 if g[p^.g]=0 then
44 begin
45 g[p^.g]:=1;
46 d[r]:=p^.g;r:=r mod 100005+1;
47 end;
48 end;
49 p:=p^.next;
50 end;
51 g[d[f]]:=0;f:=f mod 100005+1;
52 end;
53 writeln(c[n]);
54 readln;
55 end.BFS代码（好吧我承认BFS貌似还是比spfa多了一行）：
1 /**************************************************************
2 Problem: 2292
3 User: HansBug
4 Language: Pascal
5 Result: Accepted
6 Time:428 ms
7 Memory:10780 kb
8 ****************************************************************/
9
10 type
11 point=^node;
12 node=record
13 g:longint;
14 next:point;
15 end;
16 var
17 i,j,k,l,m,n,f,r,t:longint;
18 a:array[0..300005] of point;
19 c,d:array[0..300005] of longint;
20 p:point;
21 procedure add(x,y:longint);
22 var p:point;
23 begin
24 new(p);p^.g:=y;p^.next:=a[x];a[x]:=p;
25 end;
26 begin
27 readln(n,m);t:=n;
28 for i:=1 to n*2 do a[i]:=nil;
29 for i:=1 to m do
30 begin
31 readln(j,k,l);
32 if l=2 then
33 begin
34 inc(n);
35 add(j,n);add(n,k);
36 end
37 else add(j,k);
38 end;
39 fillchar(c,sizeof(c),255);d[1]:=1;f:=1;r:=2;c[1]:=0;
40 while f<r do
41 begin
42 p:=a[d[f]];
43 while p<>nil do
44 begin
45 if c[p^.g]=-1 then
46 begin
47 c[p^.g]:=c[d[f]]+1;
48 d[r]:=p^.g;inc(r);
49 end;
50 p:=p^.next;
51 end;
52 inc(f);
53 end;
54 writeln(c[t]);
55 readln;
56 end.本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015-05-08 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录