题目：点击打开链接

思路：对于当前位置的每个时间段都要走一遍（除了那些须要的时间比最大同意的时间还大的），用 整形 vis[当前位置][剩余油量] 标记。

#include <cstdio>

#include <queue>

#include <algorithm>

#define INF 999999999

using namespace std;

struct S{

int pos,time,remain;

bool operator<(const S &p) const

{

    return time>p.time;

}

}t,oldt;

int st[500][500][20],et[500][500][20],jt[500][500][20],head[500],nxt[2000],vis[500][2405],e[2000];

int main()

{

    int n,m,i,j,a,b,u,v,time;

    while(scanf("%d%d",&n,&m) && n+m)

    {

        for(i=0;i<n;i++) head[i]=-1;

        for(i=0;i<m;i++)

        {

            scanf("%d%d",&a,&b);

            nxt[i*2]=head[a];

            head[a]=i*2;

            nxt[i*2+1]=head[b];

            head[b]=i*2+1;

            e[i*2]=b;

            e[i*2+1]=a;

            for(j=0;;j++)

            {

                scanf("%d%d%d",&u,&v,&time);

                u*=10;

                v*=10;

                time*=10;

                st[a][b][j]=st[b][a][j]=u;

                et[a][b][j]=et[b][a][j]=v;

                jt[a][b][j]=jt[b][a][j]=time;

                if(v==14390) break;

            }

        }

        t.time=7200;

        t.pos=0;

        t.remain=2400;

        priority_queue<S>que;

        que.push(t);

        for(i=0;i<n;i++) for(j=0;j<2405;j++) vis[i][j]=INF;

        vis[0][t.remain]=t.time;

        while(!que.empty())

        {

            t=que.top();

            if(t.pos==n-1)

            {

                printf("%d\n",(t.time-7200)/10);

                break;

            }

            que.pop();

            oldt=t;

            for(i=head[oldt.pos];i!=-1;i=nxt[i])

            {

                for(j=0;;j++)

                {

                    if(jt[oldt.pos][e[i]][j]>2400)

                    {

                        if(et[oldt.pos][e[i]][j]<14390) continue;

                        else break;

                    }

                    t.pos=e[i];

                    if(oldt.remain>=jt[oldt.pos][e[i]][j])//假设油足够

                    {

                        t.time=oldt.time;

                        t.remain=oldt.remain;

                    }

                    else//假设油不够，先加够再说

                    {

                        t.time=oldt.time+(jt[oldt.pos][e[i]][j]-oldt.remain)*2;

                        t.remain=jt[oldt.pos][e[i]][j];

                    }

                    if(t.time%14400<st[oldt.pos][e[i]][j])

                    {

                        t.remain+=(st[oldt.pos][e[i]][j]-t.time%14400)/2;

                        if(t.remain>2400) t.remain=2400;

                        t.time+=st[oldt.pos][e[i]][j]-t.time%14400;

                    }

                    else if(t.time%14400>et[oldt.pos][e[i]][j])

                    {

                        t.remain+=(14400+st[oldt.pos][e[i]][j]-t.time%14400)/2;

                        if(t.remain>2400) t.remain=2400;

                        t.time+=14400+st[oldt.pos][e[i]][j]-t.time%14400;

                    }

                    t.time+=jt[oldt.pos][e[i]][j];

                    t.remain-=jt[oldt.pos][e[i]][j];

                    if(t.time<vis[t.pos][t.remain])

                    {

                        que.push(t);

                        vis[t.pos][t.remain]=t.time;

                    }

                    if(et[oldt.pos][e[i]][j]==14390) break;

                }

            }

        }

    }

}