国际大学生程序设计竞赛例题_2.10网络探测

1,题意:找出0到t的最小距离,要求跳数不超过10.
2,解决:
动态规划:
d[j][k]:0经过跳数k到达j的距离.
得到:d[i][k]=d[j][k-1]+g[i][j];
d[0][0]=0;
结果等于min(d[t][k],k=1,2,...,t).
3,实现代码:

#include <iostream>
using namespace std;

const int INF=0xffffff;
const int MAXN=1010;
const int MAXH=10;//最大跳数为10

int g[MAXN][MAXN];//邻接矩阵
int d[MAXN][MAXH+1];//状态矩阵


int main()
{
    freopen("2.10.in","r",stdin);
    int n;//主机数
    int m;//边数
    int t;//目标
    int ans;
    while(cin>>n,n)
    {
        ans=INF;
        for(int i=0;i<MAXN;i++)
            for(int j=0;j<=MAXH;j++)
                d[i][j]=INF;
        d[0][0]=0;
        for(int i=0;i<MAXN;i++)
            for(int j=0;j<MAXN;j++)
                g[i][j]=INF;

        cin>>m>>t;
        int u,v,dis;
        for(int i=0;i<m;i++)
        {
            cin>>u>>v>>dis;
            if(dis<g[u][v])
                g[u][v]=g[v][u]=dis;
        }
        for(int k=1;k<=MAXH;k++)
            for(int i=1;i<n;i++)
                for(int j=0;j<n;j++)
                    if( g[j][i]<INF&&(d[j][k-1]+g[j][i]<d[i][k]))
                        d[i][k]=d[j][k-1]+g[j][i];
        for(int k=0;k<=MAXH;k++)
            if(ans>d[t][k]) ans=d[t][k];
        if(ans==INF)
            cout<<"no"<<endl;
        else
            cout<<ans<<endl;
    }
    return 0;
}