POJ 1125 Stockbroker Grapevine 最短路基本题 - c++编程基础

for(j=1;j<=n;j++)
dis[i][j]=0x3f3f3f3f; //给所有点赋最大值
for(i=1;i<=n;i++)
{
scanf("%d",&p);
while(p--)
{
scanf("%d%d",&j,&k);
dis[i][j]=k; //两个点的路径(本题就是两个投资人之间通风报信的时间)入表
}
}

/*该注释能输出构建的邻接表
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
cout< cout< }
*/

//开始floyd 复杂度O(n^3)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
for(k=1;k<=n;k++)
if(dis[j][k] > dis[j][i] + dis[i][k] ) //比较两点间是直达快还是绕路快,更新邻接表
dis[j][k] = dis[j][i] + dis[i][k];

/*该注释能输出更新后的邻接表

for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
cout< cout< }
*/

//接下来就是找出( 是哪些点能走通其他所有点 && 这些点中[到其他所有点的距离的最大值]的最小值)
int min=0x7fffffff,geti;
for(i=1;i<=n;i++)
{
int max=-0x7fffffff;
for(j=1;j<=n;j++)
{
if(i!=j && dis[i][j]>max)
max= dis[i][j];
}
if(min>max)
{
min=max;
geti=i;
}
}
cout< }
return 0;
}

作者：ffq5050139

POJ 1125 Stockbroker Grapevine 最短路基本题(二)