hdu4396 多狀態spfa

題意:
給你一個圖,讓你送起點走到終點,至少經過k條邊,問你最短路徑是多少....

思路:

把每個點拆成50點,記為dis[i][j] (i 1---50 ,j 1---n);代表走到第j個點做過i條邊時的最短距離,因為做多五十條邊,如果走的過程中,邊數大於50直接等於50,因為大於50的時候就沒有必要走"回頭路"了...然後跑完spfa後在dis[i][t](i = k---50)中取一個最小的輸出來,就行了...

#include
#include
#include

#define N_node 5000 + 100
#define N_edge 200000 + 1000
#define inf 100000000

using namespace std;

typedef struct
{
   int to ,next ,cost;
}STAR;

typedef struct
{
   int x ,t;
}NODE;

int s_x[55][N_node] ,n ,m ,s ,t;
int mark[55][N_node];
int list[N_node] ,tot;
NODE xin ,tou;
STAR E[N_edge];


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()
{
   for(int i = 0 ;i <= 52 ;i ++)
   for(int j = 1 ;j <= n ;j ++)
   s_x[i][j] = inf;
  // printf("%d %d\n" ,s_x[1][3] ,s_x[1][2]);
   s_x[0][s] = 0;
   xin.x = s;
   xin.t = 0;
   queue<NODE>q;
   q.push(xin);
   memset(mark ,0 ,sizeof(mark));
   mark[0][s] = 1;
   while(!q.empty())
   {
      tou = q.front();
      q.pop();
      for(int k = list[tou.x] ;k ;k = E[k].next)
      {
         xin.x = E[k].to;
         xin.t = tou.t + 1;
         if(xin.t > 50) xin.t = 50;
         //printf("%d %d %d %d\n" ,s_x[xin.t][xin.x] ,s_x[tou.t][tou.x] + E[k].cost ,xin.t ,xin.x);
         if(s_x[xin.t][xin.x] > s_x[tou.t][tou.x] + E[k].cost)
         {
            s_x[xin.t][xin.x] = s_x[tou.t][tou.x] + E[k].cost;
            
            if(!mark[xin.t][xin.x])
            {
               mark[xin.t][xin.x] = 1;
               q.push(xin);
            }
         }
      }
   }
}

int main ()
{
   int m ,a ,b ,c ,k ,i;
   while(~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);
         add(a ,b ,c);
         add(b ,a ,c);
      }
      
      scanf("%d %d %d" ,&s ,&t ,&k);
      SPFA();
      int ans = inf;
      k = (k + 9)/10;
      for(i = k ;i <= 50 ;i ++)
      if(ans > s_x[i][t])
      ans = s_x[i][t];
      if(ans == inf) ans = -1;
      printf("%d\n" ,ans);
   }
   return 0;
}