此题数据极弱。一开始我还想到对边排序之后在搜索，后来看了题解之后发现完全没有必要！有一点要注意：题目中说不能重复走一条边，但是没有说不能走重复顶点！
以下是我的代码：
#include<stdio.h>
#define MAXN 108
#define MAXINT 200000008
long n,m,tl,v,c[MAXN][MAXN],t[MAXN][MAXN];
long ansc,anst,used[MAXN][MAXN]=
{0};
void init()
{
long i,j,a,b,t1,t2;
scanf("%ld%ld%ld%ld",&n,&m,&tl,&v);
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
{
c[i][j]=0;
t[i][j]=MAXINT;
used[i][j]=0;
}
for(i=1;i<=m;i++)
{
scanf("%ld%ld%ld%ld",&a,&b,&t1,&t2);
t[a][b]=t[b][a]=t1;
c[a][b]=c[b][a]=t2;
}
// Read In
ansc=0;anst=MAXINT;
// Ready
}
void dfs(long x,long cc,long tt)
{
long i;
if(tt>tl) return;
if(cc>v) return;
if(x==n)
{
if(cc>ansc)
{
ansc=cc;
anst=tt;
}
else if(cc==ansc&&tt<anst)
anst=tt;
return;
}
for(i=1;i<=n;i++)
{
if(c[x][i]!=0&&!used[x][i])
{
used[x][i]=used[i][x]=1;
dfs(i,cc+c[x][i],tt+t[x][i]);
used[x][i]=used[i][x]=0;
}
}
}
int main()
{
init();
dfs(1,0,0);
printf("%ld %ld\n",anst,v-ansc);
// getchar();getchar();
return 0;
}
posted on 2010-01-06 20:11
lee1r 阅读(230)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：搜索