POJ1125(folyd多源最短路)

数据输入:
n:经济人总数,图的大小;
接下来n行
m 是第i个经纪人信任的人个数
2*m 个数字分别代表那个人的编号与传播时间

找一个经纪人传播全图最快
输出那个人的编号和时间如果所有人都不能遍历全图,输出disjoint

分析:
folyd求多源最短路,然后取其中最小的
n^3的算法好就没用过了

code:

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<iostream>
#include<string>
#include <set>
using namespace std;
#define ll long long
#define mem(a) memset(a,0,sizeof(a))
const int eps=1e-8;
const int maxn=105;//须填写
const int inf=0x3f3f3f3f;
int n;
int map[maxn][maxn];
void floyd()
{
for(int k=0;k<n;k++)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(map[i][j]>map[i][k]+map[k][j])
{
map[i][j]=map[i][k]+map[k][j];
}
}
}
}
}
int main()
{
while(scanf("%d",&n)!=EOF&&n)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(j==i)
map[i][j]=0;
else
map[i][j]=inf;
}
}
for(int i=0;i<n;i++)
{
int acc,dis;
int m;
scanf("%d",&m);
for(int j=0;j<m;j++)
{
// printf("!!!!!!!n");
scanf("%d%d",&acc,&dis);
acc--;
map[i][acc]=dis;
}
}
floyd();
int start;
int mdis=inf;
for(int i=0;i<n;i++)
{
bool sign=true;
int temp=-1;
for(int j=0;j<n;j++)
{
if(i!=j&&map[i][j]>temp)
{
temp=map[i][j];
}
if(i!=j&&map[i][j]==inf)
{
sign=false;
break;
}
}
if(mdis>temp&&sign)
{
sign=true;
mdis=temp;
start=i+1;
}
}
if(mdis==inf)
{
printf("disjointn");
}
else{
printf("%d %dn",start,mdis);
}
}
return 0;
}

最后

以上就是机灵期待为你收集整理的POJ1125(folyd多源最短路)的全部内容，希望文章能够帮你解决POJ1125(folyd多源最短路)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。