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+剪枝

两遍SPFA作预处理

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

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

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

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

确实裸搜可以过的。。

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

DFS，剪枝：

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

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

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

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

by 楼下

PS：拆点最短路可做，空间不够

编译通过...

├ 测试数据 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，我是改成邻接表之后开动态数组的。。。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

这才是正解！

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

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

编译通过...

├ 测试数据 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点联出边的条数 总算过了

只过样例，倒啊~~~~~~

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

不知谁有更好的算法？

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

为这题降了2点AC率.

终于过了.

第110题.

时间稍微恶心了点

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

解题报告 http://plfxy.blog.hexun.com/24627040_d.html

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

编译通过...

├ 测试数据 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的失败就在看成“单向”),判断体力剩余和有否到达最终点，并更新最小距离。。。

第 100 道 Accept !

第 1 道 难度 = 5!

小小庆祝一下!

...

编译通过...

├ 测试数据 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

？？？？？？？？？？？？？