题解

104 条题解

  • 0
    @ 2009-01-17 20:00:46

    var

    i,j,k,n,m,w,x,y,q,o,vv:longint;

    a,b,c,d,ss,ww:array[0..100000]of longint;

    g:array[0..100000]of boolean;

    procedure li(x:longint);

    var

    i:longint;

    begin

    if x=y

    then begin

    if k=0)and(g[i])

    then begin

    g[i]:=false;

    dec(w,c[i]);

    inc(k,d[i]);

    li(b[i]);

    inc(w,c[i]);

    dec(k,d[i]);

    g[i]:=true;

    end;

    end;

    end;

    procedure pai(l,r:longint);

    var

    i,j,k,mid:longint;

    begin

    i:=l;

    j:=r;

    mid:=a[(l+r) div 2];

    repeat

    while a[i]mid do dec(j);

    if ij;

    if il then pai(l,j);

    end;

    begin

    readln(n,m);

    for i:=1 to m do

    readln(a[i],b[i],c[i],d[i]);

    for i:=m+1 to 2*m do

    begin

    a[i]:=b;

    b[i]:=a;

    c[i]:=c;

    d[i]:=d;

    end;

    pai(1,2*m);

    readln(x,y);

    readln(w);

    a[0]:=-1;

    k:=0;

    for i:=1 to 2*m do

    begin

    if a[i]a

    then begin

    inc(k);

    ss[a[i]]:=i;

    ww[a]:=i-1;

    end;

    end;

    ww[a[i]]:=i;

    vv:=maxlongint;

    fillchar(g,sizeof(g),true);

    for i:=ss[x] to ww[x] do

    begin

    k:=0;

    if w>=c[i]

    then begin

    g[i]:=false;

    dec(w,c[i]);

    inc(k,d[i]);

    li(b[i]);

    g[i]:=true;

    inc(w,c[i]);

    end;

    end;

    if vv=maxlongint

    then write(-1)

    else write(vv);

    end.

    快排+DFS+剪枝

  • 0
    @ 2009-01-03 15:03:27

    两遍SPFA作预处理

    再来一个SPFA+双重剪枝,AC

    把点用一个队列替代,首先用可行性剪去一些队列中的元素。再不断地用最优性删除已存在队列中的元素。

    可以过随机数据:k=10^9,50000个节点,1000000条边

  • 0
    @ 2008-11-13 16:00:25

    把边都存一块儿,按照起点排序,then dfs,then 0ms AC.

  • 0
    @ 2008-11-12 09:04:17

    确实裸搜可以过的。。

    就是我没事做写了个链表,不过其实也不怎么难写。。

  • 0
    @ 2008-11-11 21:16:59

    DFS,剪枝:

    1.当前体力已经超过K就不用搜

    2.当前时间超过目前最少时间就不用搜

    3.用B表示第I个点的最少时间,C表示在B取到最小时的第I个点的体力

    当某一点的两个权值都超过B与C时不搜

    by 楼下

    PS:拆点最短路可做,空间不够

  • 0
    @ 2008-11-08 17:16:22

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    直接DFS+最优性剪枝

    图不能用邻接矩阵存,会MLE,我是改成邻接表之后开动态数组的。。。

  • 0
    @ 2008-11-06 22:01:55

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    “拆点”的spfa!!!还要用队列维护!!(弱数据可能不维护都可以过)

    下面用搜索过的可能是因为数据弱吧?

    这才是正解!

  • 0
    @ 2008-10-29 19:25:24

    刚开始时开两个5000*5000,后两点超内存,晕倒

  • 0
    @ 2008-10-29 10:08:09

    只过样例是因为你把它当成有向图了吧。。。

  • 0
    @ 2008-10-28 21:41:58

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    我也算得经验丰富了

    先超时+超内存

    然后改成前向星 超时一个点

    然后排序 再枚举边 继续超时

    最后 用了p记录点的位置 l点联出边的条数 总算过了

  • 0
    @ 2008-10-27 18:06:19

    只过样例,倒啊~~~~~~

  • 0
    @ 2008-10-27 16:32:21

    我不认为此题标准算法是搜索,我用的dfs,不过我认为过了纯粹是数据弱。

    不知谁有更好的算法?

  • 0
    @ 2008-10-25 10:58:45

    双向的注意!非矩阵存图很容易写成单向的了

  • 0
    @ 2008-10-25 09:54:06

    为这题降了2点AC率.

    终于过了.

    第110题.

  • 0
    @ 2008-10-23 13:09:28

    时间稍微恶心了点

    题目巨简单...我没怎么加剪枝就过了...

  • 0
    @ 2008-10-21 19:53:51
  • 0
    @ 2008-10-20 22:57:24

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    做这题时无聊,尝试了用了一下Pascal的动态数组。。。(其实没必要)

  • 0
    @ 2008-10-16 00:46:53

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    失败啊,对循环队列的spfa不熟,2h都没搞定。。。(╯﹏╰)

    最后用10min写了个破败的DFS。。。0ms。。。(O__O")

    用map数组记录边的x,y,c,d;a数组模拟邻接表,a表示点s发出的边数。

    dfs(s,c,d)……搜索从点s发起,剩下体力c,已行走距离d的状态。。。

    i=1~a,一条边的两端同时搜(spfa的失败就在看成“单向”),判断体力剩余和有否到达最终点,并更新最小距离。。。

  • 0
    @ 2008-10-10 12:46:44

    第 100 道 Accept !

    第 1 道 难度 = 5!

    小小庆祝一下!

    ...

  • 0
    @ 2008-10-18 06:50:23

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:运行超时...

    ├ 测试数据 03:运行超时...

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:内存溢出...

    ├ 测试数据 09:内存溢出...

    ├ 测试数据 10:内存溢出...

    ---|---|---|---|---|---|---|---|-

    Unaccepted 有效得分:50 有效耗时:0ms

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案错误...程序输出比正确答案长

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:内存溢出...

    ├ 测试数据 09:内存溢出...

    ├ 测试数据 10:内存溢出...

    ---|---|---|---|---|---|---|---|-

    Unaccepted 有效得分:60 有效耗时:0ms

    啊啊

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    为什么?

    为什么?

    用点作DFS

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 9ms

    ├ 测试数据 08:运行超时|无输出...

    ├ 测试数据 09:内存溢出...

    ├ 测试数据 10:运行超时|无输出...

    ---|---|---|---|---|---|---|---|-

    Unaccepted 有效得分:70 有效耗时:9ms

    用边作DFS就

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    ?????????????

信息

ID
1082
难度
7
分类
图结构 | 最短路 点击显示
标签
(无)
递交数
2117
已通过
488
通过率
23%
被复制
5
上传者