题意:
给出若干个联系人,及每个联系人通知其他联系人所需的时间,求从哪个联系人开始通知所用时间最短,并求出最短时间。
很明显是图论中求最短路径问题,可以用floyd 算法或者Dijkstra算法。我这里分别用两种方法实现。
方法一:Dijkstra算法。
只要遍历每个人,对每个人都以他为起点调用Dijkstra算法,求出最长时间(注意这道题一个联系人可以同时通知多个联系 人,所以求出他通知他人的最大时间,则是他通知所以人所用时间)。然后在每个人的“最长时间中”求出最短的那个。即答案。
#include "iostream" using namespace std; #define len 110 #define MAXINT 9999999 int map[len][len]; int length[len];//记录v到length[k]的最短路径 int flag[len];//标记某点是否得到最短路径(即处理完毕) int dis(int v,int num)//此方法即Dijkstra算法 { int i; int j; for ( i=1;i<=num;i++) { length[i]=map[v][i];//初始化第一组数据 flag[i]=0; } length[v]=0; flag[v]=1; for (i=1;i<num;i++) { int min=MAXINT; int minindex=-1; for (j=1;j<=num;j++)//找到本次搜索中距离最小的那个 { if (flag[j]==0&&j!=v) if (length[j]<min) { min=length[j]; minindex=j; } } if (minindex!=-1) { flag[minindex]=1;//将本次搜索中最小的那个加入以已处理集合(即已经找到最短路径) for (j=1;j<=num;j++) { if (flag[j]==0)//更新未处理的点 { if (length[j]>length[minindex]+map[minindex][j]) { length[j]=length[minindex]+map[minindex][j]; } } } } } int max=-1; for (i=1;i<=num;i++) { if (max<length[i]) { max=length[i]; } } return max;//返回最大的一条边 } int main() { int num; int i,j; while(true) { scanf("%d",&num);//num表示有几个人 if (num==0) { break; } for (i=1;i<=num;i++) { int n; scanf("%d",&n); for (j=1;j<=num;j++) { map[i][j]=MAXINT;//这里不能用memset方法,memset方法只能初始化为0 ,1,-1 } for (j=1;j<=n;j++) { int t; scanf("%d",&t); scanf("%d",&map[i][t]); } } int min=MAXINT;//记录最短的时间 int mini=1;//记录从哪个联系人开始 for (i=1;i<=num;i++)//对每个联系人遍历 { if (min>dis(i,num)) { min=dis(i,num); mini=i; } } if (min>100) { printf("disjoint\n"); } else { printf("%d %d\n",mini,min); } } return 0; }
方法二:floyd算法
floyd算法是用来求图中的两点到两点之间的最短距离.。
其状态转移方程为: dp[i][j]=min(dp[i][k]+dp[k][j],dp[i][j]);dp[i][j]为点i到点j的最短路径,k为中间点.
于是我们可以很简单写出floyd的代码
for (i=1;i<=num;i++) { for (j=1;j<=num;j++) { for (int k=1;k<=num;k++) { if (dp[i][j]>dp[i][k]+dp[k][j]) { dp[i][j]=dp[i][k]+dp[k][j]; } } } }那么上述代码有没有问题呢?
相关推荐
北大POJ1125-Stockbroker Grapevine【Floyd】 解题报告+AC代码
北大POJ初级-图算法 解题报告+AC代码
北大POJ初级-基本算法 解题报告+AC代码
北大POJ中级-基本算法 解题报告+AC代码
北大POJ2002-Squares 解题报告+AC代码
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
poj 1000 - 2000 部分题目 官方分类 poj 1000 - 2000 部分题目 官方分类
北大POJ1062-Expensive dowry【dijkstra】 解题报告+AC代码
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ3020-Antenna Placement 解题报告+AC代码
这是魔兽世界终极版POJ的-测试数据,找了好久才找到的。 本来想设置为0积分,但是它居然自动收费(o_ _)ノ。 看传送门:https://pan.baidu.com/s/1cCIwW8psGDASu2JdZawG3Q
北大POJ3414-Pots 解题报告+AC代码
POJ3211--Washing Clothes
北大POJ2305-Basic remains POJ2305-Basic remains
北大POJ1321-Chess Problem POJ1321-Chess Problem
北大POJ1080-Human Gene Functions POJ1080-Human Gene Functions
POJ---1456.Supermarket测试数据及答案,题目描述:A supermarket has a set Prod of products on sale. It earns a profit px for each product x∈Prod sold by a deadline dx that is measured as an integral ...
poj 1000-3000部分代码 网上收集
POJ 1038--Bugs Integrated
POJ3036--Honeycomb Walk