边数限制最短路

本文主要是介绍边数限制最短路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

从0到t，经过边数不超过10的最短路.

sp[i][k]代表从0到i经过k条边的最短路长度。

#include<iostream>
#include<algorithm>
#include<queue>
#include<string.h>
#include<cstdio>
using namespace std;#define INF 1<<20
#define MAXN 1010
#define MAXH 10long d[MAXN][MAXN];
long sp[MAXN][MAXH+1];
long n,m,t;void init()
{long i,j,a,b,c;for(i=0;i<n;i++)for(j=0;j<n;j++)d[i][j]=INF;for(i=0;i<n;i++)for(j=0;j<=MAXH;j++)sp[i][j]=INF;sp[0][0]=0;while(m--){scanf("%ld%ld%ld",&a,&b,&c);if(c<d[a][b])d[a][b]=c;if(c<d[b][a])d[b][a]=c;}
}void dp()
{long i,j,k;for(k=1;k<=MAXH;k++)for(i=0;i<n;i++)for(j=0;j<n;j++)if(d[j][i]<INF&&sp[j][k-1]+d[j][i]<sp[i][k])sp[i][k]=sp[j][k-1]+d[j][i];
}int main()
{while(scanf("%ld%ld%ld",&n,&m,&t),n){init();dp();long answer=INF;for(long i=0;i<=MAXH;i++){if(sp[t][i]<answer)answer=sp[t][i];}if(answer==INF)printf("no\n");else printf("%ld\n",answer);}return 0;
}

这篇关于边数限制最短路的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---