poj 1724 ROADS

　　这道题跟poj 3411 差不多，不过这道题得用邻接表，不然就超时了，这道题我的代码跑了63MS，324K，我瞅了一下列表，好多人都跑了0MS，你NB！！

　　DFS。

　　题意：有n 城市，r条路，有k这么多的钱。不同的路花费不一样，求从1到n最快且总花费不超过k的长度。这道题用邻接表还是比较快的，用POJ3411那道题用的保存信息的结构果断超时啊啊啊。。。用邻接表也TLE了几次，最后由增加了几句 if 语句，才算AC。

/*
FUCK!! 终于不超时了
*/
#include<stdio.h>
#include<string.h>

struct node {
    int d,t,l;
    int next;
}road[10010];
int head[110],visit[110];
const int inf = 99999999;
int minlen,tot;
int k,n,r;
void Build(int s,int d,int l,int t)
{
    road[tot].d=d;road[tot].t=t;
    road[tot].l=l;road[tot].next=head[s];
    head[s]=tot++;
}
void DFS(int a,int len,int fee)
{
    if(a==n && fee<=k && minlen>len)
    {
        minlen=len;
        return ;
    }
    if(len>=minlen) return;
    if(fee>k)   return;
    if(a==n)    return;
    for(int i=head[a];i!=-1;i=road[i].next)
    {
        if(road[i].t+fee<=k && !visit[road[i].d])
        {
            int b=road[i].d;
            visit[b]++;
            DFS(b,road[i].l+len,road[i].t+fee);
            visit[b]--;
        }
    }
}
int main()
{
    int s,d,l,t;
    while(scanf("%d%d%d",&k,&n,&r)!=EOF)
    {
        tot=0;
        memset(head,-1,sizeof(head));
        memset(visit,0,sizeof(visit));

        for(int i=1;i<=r;i++)
        {
            scanf("%d%d%d%d",&s,&d,&l,&t);
            Build(s,d,l,t);
        }

        minlen=inf;

        DFS(1,0,0);

        if(minlen==inf)
            printf("-1
");
        else
            printf("%d
",minlen);
    }
    return 0;
}