此題數據極弱。一開始我還想到對邊排序之后在搜索，后來看了題解之后發現完全沒有必要！有一點要注意：題目中說不能重復走一條邊，但是沒有說不能走重復頂點！
以下是我的代碼：
#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 閱讀(245)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：搜索