hdu4284 dfs+floyd

题意:

给你n个城市,m条边,要有h个必须旅游和打工的城市,问你能不能从1把所有必须的h个城市全部旅游并且打工完...

思路:

先一遍floyd跑出全局最短路,然后暴力枚举出打工的顺序,当打工的个数达到h的时候判断下是否能从第h个打工的点用当前剩余的前回到1如果能就ok..

#include<stdio.h>

#include<string.h>

#define inf 1000000000



int map[100+50][100+50];

int H[20] ,C[20] ,D[20];

int HH[20];

int minn(int a ,int b)

{

   return a < b ? a : b;

}

void floyd(int n)

{

   for(int k = 1 ;k <= n ;k ++)

   for(int i = 1 ;i <= n ;i ++)

   for(int j = 1 ;j <= n ;j ++)

   map[i][j] = minn(map[i][k] + map[k][j] ,map[i][j]);

}

int mark[20] ,ok ,H_n;

void DFS(int s ,int mony ,int sum)

{

   if(sum == H_n && mony >= map[s][1])

   {

      ok = 1;

      return;

   }

   for(int i = 1 ;i <= H_n ;i ++)

   {

      if(mark[i]) continue;

      if(mony < map[s][H[i]]) continue;

      if(mony  - map[s][H[i]] >= D[i] && !ok)

      {

         mark[i] = 1;

         DFS(H[i] ,mony - map[s][H[i]] - D[i] + C[i] ,sum + 1);

         mark[i] = 0;

      }

   }

}

int main ()

{

   int i ,j ,m ,n ,mon ,t ,a ,b ,c;

   scanf("%d" ,&t);

   while(t--)

   {

      scanf("%d %d %d" ,&n ,&m ,&mon);

      for(i = 1 ;i <= n ;i ++)

      {

         for(j = 1 ;j <= n ;j ++)

         map[i][j] = inf;

         map[i][i] = 0;

      }

      for(i = 1 ;i <= m ;i ++)

      {

         scanf("%d %d %d" ,&a ,&b ,&c);

         map[a][b] = map[b][a] = minn(c ,map[a][b]);

      }

      floyd(n);

      scanf("%d" ,&H_n);

      memset(mark ,0 ,sizeof(mark));

      for(i = 1 ;i <= H_n ;i ++)

      {

         scanf("%d %d %d" ,&H[i] ,&C[i] ,&D[i]);

      }

      ok = 0;

      DFS(1 ,mon ,0);

      if(ok) printf("YES\n");

      else printf("NO\n");

   }

   return 0;

}

巴特西

hdu4284 dfs+floyd

最新文章

热门文章