专栏首页HansBug's Lab2292: 【POJ Challenge 】永远挑战

2292: 【POJ Challenge 】永远挑战

2292: 【POJ Challenge 】永远挑战

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 553  Solved: 230

[Submit][Status][Discuss]

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行: 三个整数 UiViWi (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.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 1131: [POI2008]Sta

    1131: [POI2008]Sta Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 783  Solved:...

    HansBug
  • 3522: [Poi2014]Hotel

    3522: [Poi2014]Hotel Time Limit: 20 Sec  Memory Limit: 128 MB Submit: 253  Solve...

    HansBug
  • 算法模板——Dinic网络最大流 2

    实现功能:同Dinic网络最大流 1 这个新的想法源于Dinic费用流算法。。。 在费用流算法里面,每次处理一条最短路,是通过spfa的过程中就记录下来,然后顺...

    HansBug
  • 1131: [POI2008]Sta

    1131: [POI2008]Sta Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 783  Solved:...

    HansBug
  • 算法模板——Dinic网络最大流 2

    实现功能:同Dinic网络最大流 1 这个新的想法源于Dinic费用流算法。。。 在费用流算法里面,每次处理一条最短路,是通过spfa的过程中就记录下来,然后顺...

    HansBug
  • 算法模板——Dinic最小费用最大流

    实现功能:输入M,N,S,T;接下来M行输入M条弧的信息(包括起点,终点,流量,单位费用);实现功能是求出以S为源点,T为汇点的网络最大流的最小费用 其实相当的...

    HansBug
  • 1601: [Usaco2008 Oct]灌水

    1601: [Usaco2008 Oct]灌水 Time Limit: 5 Sec  Memory Limit: 162 MB Submit: 1342  S...

    HansBug
  • 算法模板——计算几何2(二维凸包——Andrew算法)

    实现功能:求出二维平面内一对散点的凸包(详见Codevs 1298) 很神奇的算法——先将各个点按坐标排序,然后像我们所知的那样一路左转,求出半边的凸包,然后反...

    HansBug
  • Confluence 6 数据库整合的限制 原

    注意: Confluence 自带的 XML 方式导出方法并不适用于备份和整合大数据集。这里有一些第三方的数据库工具你可以使用能够帮助你对大数据集进行备份和整合...

    HoneyMoose
  • MySQL row格式的两个问题

    作者简介: ? 刘伟 云和恩墨开源解决方案事业部首席架构师 多年一线互联网企业DBA经历,对MySQL、NoSQL,PostgreSQL等各类开源数据库均有涉猎...

    数据和云

扫码关注云+社区

领取腾讯云代金券