HDOJ 4284-Travel解题报告

亚洲区天津赛区网络预选赛的一道题，简单的搜索，但是搜索的时候最好把开始点1拆为两个节点，如果1不是必经节点，那么拆不拆都无所谓，如果1是必经节点，那么在刚开始在1的时候选择工作还是到最后再工作就要分情况，所以要进行拆点。

View Code

1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #define N 105
 5 #define inf 0x7fffffff
 6 using namespace std;
 7 int map[N][N];
 8 int c[N],d[N],f[18];
 9 int h;
10 bool dfs(int u,int mon,int state)
11 {
12     if(mon<c[u])
13     return false;
14     if(state==(1<<h)-1)
15     return true;
16     mon-=c[u];
17     mon+=d[u];
18     int i,j,v,sta;
19     for(i=0;i<h;i++)
20     {
21         if(!(state&(1<<i)))
22         {
23             if(dfs(f[i],mon-map[u][f[i]],state|(1<<i)))
24             return true;
25         }
26     }
27     return false;
28 }
29 int main()
30 {
31     int n,m,i,j,k,mon,u,v,w;
32     int t;
33     scanf("%d",&t);
34     while(t--)
35     {
36         scanf("%d%d%d",&n,&m,&mon);
37         for(i=1;i<=n;i++)
38         for(j=1;j<=n;j++)
39         map[i][j]=inf;
40         for(i=1;i<=n;i++)
41         map[i][i]=0;
42         for(i=0;i<m;i++)
43         {
44             scanf("%d%d%d",&u,&v,&w);
45             if(map[u][v]>w)
46             map[u][v]=map[v][u]=w;
47         }
48         for(k=1;k<=n;k++)
49         for(i=1;i<=n;i++)
50         for(j=1;j<=n;j++)
51         {
52             if(map[i][k]!=inf&&map[k][j]!=inf&&map[i][k]+map[k][j]<map[i][j])
53             map[i][j]=map[i][k]+map[k][j];
54         }
55         for(i=1;i<=n;i++)
56         map[n+1][i]=map[i][n+1]=map[1][i];
57         scanf("%d",&h);
58         memset(c,0,sizeof(c));
59         memset(d,0,sizeof(d));
60         int id=-1;
61         for(i=0;i<h;i++)
62         {
63             scanf("%d",&f[i]);
64             if(f[i]==1)
65             id=i;
66             scanf("%d%d",&d[f[i]],&c[f[i]]);
67         }
68         c[n+1]=c[1];
69         d[n+1]=d[1];
70         f[h]=n+1;
71         h++;
72         c[1]=d[1]=0;
73         int num=(id==-1)?0:(1<<id);
74         bool temp=dfs(1,mon,num);
75         if(temp)
76         printf("YES\n");
77         else
78         printf("NO\n");
79     }
80     return 0;
81 }      

转载于:https://www.cnblogs.com/caozhenhai/archive/2012/09/11/2679990.html