soj 1700 ping_简单dp

题意：给你一个无向图，求n边的最短路

思路：用最短路想了半天都没想出来，比赛结束回去看看原来用dp做，我的dp有待提高啊

sp[i][k]=min(sp[j][k-1]+dp[j][i])//k为多少条边，j能到i

#include <iostream>

#include<cstdio>

#include<cstdio>

using namespace std;

#define INF 0xfffffff

#define MAXN 1100

#define MAXH 10

int d[MAXN][MAXN];

int sp[MAXN][MAXH+10];

int n,m,t;

void init(){

	int 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("%d%d%d",&a,&b,&c);

		if(d[a][b]>c){//判重边

			d[a][b]=d[b][a]=c;

		}

	}

}

int main(int argc, char** argv) {

	int i,j,k;

	while(scanf("%d%d%d",&n,&m,&t)!=EOF,n){

		init();

		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];//当 j能到i时更新最短路

		}

		int ans=INF;

		for(i=0;i<=MAXH;i++)//最多10条边

			if(sp[t][i]<ans)

				ans=sp[t][i];

		if(ans==INF)

			printf("no\n");

		else

			printf("%d\n",ans);

	}

	return 0;

}