hdu4396 多状态spfa

思路:

把每个点拆成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
     ; }