求至少经过K条边，到达终点的最短路（K<=50）。
K比较小，先用Bellman求出走50步到达每个点的最短路，然后把50步的可达点加到队列里SPFA即可。
题解是直接二维最短路的，不过好像比bellman+spfa慢。。目前排在HDOJ第一。。
1 #include <string.h> 2 #include <stdio.h> 3 #include <queue> 4 #define MAXN 5005 5 #define MAXE 200005 6 #define INF 0x3f3f3f3f 7 struct edge{ 8 int u,v,n,w; 9 }e[MAXE]; 10 int first[MAXN],es; 11 int tu,tv,tw; 12 int s,t,k,n,m; 13 void addedge(int u,int v,int w){ 14 e[es].u=u,e[es].v=v,e[es].w=w; 15 e[es].n=first[u],first[u]=es++; 16 } 17 int dd[52][MAXN]; 18 void bellman(){ 19 memset(dd,0x3f,sizeof dd); 20 dd[0][s]=0; 21 for(int i=1;i<=k;i++)for(int j=0;j<es;j++) 22 if(dd[i][e[j].v]>dd[i-1][e[j].u]+e[j].w) 23 dd[i][e[j].v]=dd[i-1][e[j].u]+e[j].w; 24 } 25 bool inq[MAXN]; 26 int spfa(){ 27 std::queue<int> q; 28 memset(inq,0,sizeof inq); 29 for(int i=1;i<=n;i++) 30 if(dd[k][i]!=INF)q.push(i); 31 while(!q.empty()){ 32 int u=q.front();q.pop(); 33 inq[u]=0; 34 for(int i=first[u];i!=-1;i=e[i].n){ 35 int v=e[i].v; 36 if(dd[k][v]>dd[k][u]+e[i].w){ 37 dd[k][v]=dd[k][u]+e[i].w; 38 if(!inq[v])q.push(v),inq[v]=1; 39 } 40 } 41 } 42 return dd[k][t]==INF?-1:dd[k][t]; 43 } 44 int main(){ 45 //freopen("test.in","r",stdin); 46 while(scanf("%d%d",&n,&m)!=EOF){ 47 memset(first,-1,sizeof first);es=0; 48 for(int i=0;i<m;i++){ 49 scanf("%d%d%d",&tu,&tv,&tw); 50 addedge(tu,tv,tw); 51 addedge(tv,tu,tw); 52 } 53 scanf("%d%d%d",&s,&t,&k); 54 k=(k+9)/10; 55 bellman(); 56 printf("%d\n",spfa()); 57 } 58 return 0; 59 }