hdu3768 spfa+全排列

题意:

给你一个无向图,和一些必须经过的点,问你从起点出发,到达所有必须经过的点再回来的最小总路径.

思路:

因为必须经过的点的数量很小,小于等于10,全排列是 10! = 3628800 所以以每个必须经过的点为起点跑最短路,记录数值,然后全排列,枚举经过顺序,取得最小就行了..

#include<stdio.h>

#include<string.h>

#include<queue>

#include<algorithm>

#define N_node (100000 + 500)

#define N_edge (200000 + 1000)

#define INF 1000000000



using namespace std;

typedef struct

{

   int to ,next ,cost;

}STAR;

STAR E[N_edge];

int list[N_node] ,tot;

int s_x[N_node];

int s_x2[12][N_node];

int mk_node[12];

int hash[N_node];

void add(int a ,int b ,int c)

{

   E[++tot].to = b;

   E[tot].cost = c;

   E[tot].next = list[a];

   list[a] = tot;

}

void SPFA(int s ,int n)

{

   int mark[N_node] = {0};

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

   s_x[i] = INF;

   mark[s]  = 1;

   s_x[s] = 0;

   queue<int>q;

   q.push(s);

   while(!q.empty())

   {

      int xin ,tou;

      tou = q.front();

      q.pop();

      mark[tou] = 0;

      for(int k = list[tou] ;k ;k = E[k].next)

      {

         xin = E[k].to;

         if(s_x[xin] > s_x[tou] + E[k].cost)

         {

            s_x[xin] = s_x[tou] + E[k].cost;

            if(!mark[xin])

            {

               mark[xin] = 1;

               q.push(xin);

            }

         }

      }

   }

   return ;

}

int main ()

{

   int t ,n ,m ,i;

   int a ,b ,c ,s;

   scanf("%d" ,&t);

   while(t--)

   {

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

      memset(list ,0 ,sizeof(list));

      tot = 1;

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

      {

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

         a++ ,b++;

         add(a ,b ,c) ,add(b ,a ,c);

      }

      scanf("%d" ,&s);

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

      {

         scanf("%d" ,&mk_node[i]);

         mk_node[i]++;

         hash[mk_node[i]] = i;

      }

      mk_node[0] = 1;

      for(i = 0 ;i <= s ;i ++)

      {

         SPFA(mk_node[i] ,n);

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

         s_x2[i][j] = s_x[j];

      }

      int max = 1;

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

      max *= i;

      int ans_min = INF;

      while(max --)

      {

         int tmp = s_x2[0][mk_node[1]] + s_x2[hash[mk_node[s]]][1];

         for(i = 2 ;i <= s ;i ++)

         tmp += s_x2[hash[mk_node[i-1]]][mk_node[i]];

         if(ans_min > tmp) ans_min = tmp;

         next_permutation(mk_node + 1 ,mk_node + s + 1);

      }

      printf("%d\n" ,ans_min);

   }

   return 0;

}

巴特西

hdu3768 spfa+全排列

最新文章

热门文章