poj 1724

Description

Input

Output

Sample Input

5
6
7
1 2 2 3
2 4 3 3
3 4 2 4
1 3 4 1
4 6 2 1
3 5 2 0
5 4 3 2

Sample Output

11

Source

CEOI 1998

用vector超时了

AC代码：

#include<limits.h>
#include<vector>
#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
struct Node{
    int to,next;
    int len,pri;
}Edge[10005];
int index;
int head[105];
void add(int x,int y,int len,int pri){
    Edge[++index].to=y;
    Edge[index].len=len;
    Edge[index].pri=pri;
    Edge[index].next=head[x];
    head[x]=index;
}
int n,clen;
int vis[105];
void dfs(int x,int len,int k){
    if(x==n){
        if(len<clen && k>=0){
            clen=len;
        }
        return ;
    }
    if(len>clen)
        return ;
    for(int i=head[x];i;i=Edge[i].next){
        int v=Edge[i].to;
        int pri=Edge[i].pri;
        int tlen=Edge[i].len;
        if(!vis[v] && k>=pri){
            vis[v]=1;
            dfs(v,len+tlen,k-pri);
            vis[v]=0;
        }
    }
    return ;
}
int main(){
    int m,k;
    while(scanf("%d%d%d",&k,&n,&m)!=EOF){
        for(int i=1;i<=n;i++){
            head[i]=vis[i]=0;
        }
        vis[1]=1;
        index=0;
        for(int i=1;i<=m;i++){
            int x,y,len,pri;
            scanf("%d%d%d%d",&x,&y,&len,&pri);
            add(x,y,len,pri);
        }
        clen=INT_MAX;
        dfs(1,0,k);
        if(clen==INT_MAX)
            printf("-1\n");
        else
            printf("%d\n",clen);
    }
    return 0;
}

poj 1724

原文：http://blog.csdn.net/my_acm/article/details/38850445