本文主要是介绍poj 动态规划DP - 1125 Stockbroker Grapevine，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
从今天开始刷动态规划类题目，先从简单的开始，这里有一份DP题目列表点击打开链接，大家想专门刷DP的可以看一下。
1125题就是一道连通题，股票经纪人之间互传谣言，但是每个人传到其他人的时间不同，求出传播最快的那个人和所需时间。
我们可以看出这是一道求最短路径题，所以想起了Floyd算法，由于Floyd算法实现的简单性，所以绝大部分的最短路径题都是由Floyd算法解决的。
Floyd算法说白了就是遍历所有三点连接情况，如果x-d-y比x-y更短的话，则将x-y替换成x-d-y，遍历完后，我们会求得所有距离的最优解。想细细了解Floyd算法的可以去百度一下。
# include<stdio.h>
# define MAX 102
# define max(x,y) (x>y ? x:y)
int map[MAX][MAX];
int n;
void init(){for(int i =1;i<=n;i++){for(int j=1;j<=n;j++){if(i==j)map[i][j]=0;else map[i][j]=1<<29;}}
}void dp(){int i,j,k;for(k=1;k<=n;k++){for(i=1;i<=n;i++){for(j=1;j<=n;j++){if(map[i][j]>map[i][k]+map[k][j]){map[i][j] = map[i][k]+map[k][j];}}}}int mind = -1,mval = 1<<29,nval;for(i=1;i<=n;i++){nval=0;for(k=1;k<=n;k++){if(i!=k) nval =max(nval,map[i][k]);}if(nval<mval){mind = i;mval = nval;}}printf("%d %d\n",mind,mval);
}
int main(){int i,m,j,y,d;while(scanf("%d",&n) && n!=0){init();for(i=1;i<=n;i++){scanf("%d",&m);for(j=1;j<=m;j++){scanf("%d %d",&y,&d);map[i][y]=d;}}dp();}
}
这篇关于poj 动态规划DP - 1125 Stockbroker Grapevine的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
