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

思路:

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

#include<stdio.h> #include<string.h> #include<queue>#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(); mark[tou.t][tou.x] = 0;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; }

總結

以上是生活随笔為你收集整理的hdu4396 多状态spfa的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。