problem_roads.cpp

ACM中南大学 H道路的算法

//Algorithm : DFS+Cut 
//2005-10-6
#include <stdio.h>
#include <string.h>
const int M=10001,N=101,maxN=1000000000;
struct Node{
    int d,l,t;
}es[M];
int e[N][101],top[N],n,k,min=maxN,minLen[N][M];

void dfs(int v,int k,int len){
    int i;
    if (k<0 || len >= min || len>=minLen[v][k]) return ;
    if (v==n-1){
        min=len;
        return ;
    }    
    else{        
        for (i=0;i<=k;i++){
            if (len<minLen[v][i]) minLen[v][i]=len;
        
        }    
        for (i=0;i<top[v];i++){
            dfs(es[e[v][i]].d, k - es[e[v][i]].t,len + es[e[v][i]].l);
        }    
    }    
}    
int main(){
    int i,r;
    scanf("%d%d%d",&k,&n,&r);
    memset(top,0,sizeof(top));
    memset(minLen,1,sizeof(minLen));
    for (i=0;i<r;i++){
        int s;
        scanf("%d%d%d%d",&s,&es[i].d,&es[i].l,&es[i].t);
        s--; es[i].d--;
        e[s][top[s]]=i;
        top[s]++;
    }  
    dfs(0,k,0);
    
    if (min!=maxN) printf("%d\n",min);
    else printf("-1\n");
    return 0;
}