去年NOIPPJ4我也是不同于常人,BFS过的.这道题也是233333.

所以看到有限制的最短路,经典算法(如不改变)都不再有效.
最好办法就是写一个BFS/DFS.

BFS里面也可以用DFS的剪枝的.
顺便空间10000K丧心病狂,POJ不给pascal uses math 丧心病狂

program poj1062;

type pnode=^tnode;
     tnode=record
        n,w:longint;
        next:pnode;
     end;
     qnode=record
        cost,rl,rr,now:longint;
        v:array[1..100] of boolean; //还可以位运算压一压.
     end;

var g:array[1..110] of pnode;
    pr,price:array[1..110] of longint;
    abd:array[1..110] of boolean;
    n,m,ans,he,tl,source:longint;
    q:array[1..75000] of qnode;

function max(a,b:longint):longint; begin
if a>b then exit(a) else exit(b);  end;

function min(a,b:longint):longint; begin
if a<b then exit(a) else exit(b);  end;

procedure init;
var i,j,k,t:longint;
    tmp:pnode;
begin
readln(m,n);
ans:=maxlongint;
for i:=1 to n do begin
        readln(price[i],pr[i],t);
        if (i>1)and(((pr[i]+m<pr[1])or(pr[i]-m>pr[1]))or(price[i]>price[1])) then
                abd[i]:=true;
        while t>0 do begin
                dec(t);
                readln(j,k);
                new(tmp);
                with tmp^ do begin
                        n:=i;
                        w:=k;
                        next:=g[j];
                end;
                g[j]:=tmp;
        end;
end;
g[1]:=nil;
end;

procedure bfs(src:longint);
var head,tail:qnode;
    tmp:pnode;
begin
he:=0; tl:=1;
with head do begin
        cost:=price[src];
        now:=src;
        rl:=pr[src]-m;
        rr:=pr[src]+m;
        fillchar(v,sizeof(v),false);
        v[now]:=true;
end;
q[1]:=head;

while he<tl do begin
        inc(he);
        head:=q[he];
        if head.now=1 then
                ans:=min(ans,head.cost);

        tmp:=g[head.now];
        while tmp<>nil do begin
                if (not abd[tmp^.n])and(not head.v[tmp^.n])
                and(head.cost+tmp^.w<ans)
                and((pr[tmp^.n]>=head.rl)and(pr[tmp^.n]<=head.rr)) then begin
                        with tail do begin
                                now:=tmp^.n;
                                cost:=head.cost+tmp^.w;
                                rl:=max(head.rl,pr[tmp^.n]-m);
                                rr:=min(head.rr,pr[tmp^.n]+m);
                                v:=head.v;
                                v[tmp^.n]:=true;
                        end;
                        inc(tl);
                        q[tl]:=tail;
                        if tl>74997 then exit;//以免爆
                end;
                tmp:=tmp^.next;
        end;

end;
end;

begin
init;
for source:=1 to n do
        if not abd[source] then bfs(source);
writeln(ans);
end.