首页 > 代码库 > Wikioi 1020 孪生蜘蛛 Label:Floyd最短路
Wikioi 1020 孪生蜘蛛 Label:Floyd最短路
题目描述 Description
在G城保卫战中,超级孪生蜘蛛Phantom001和Phantom002作为第三层防卫被派往守护内城南端一带极为隐秘的通道。
根据防护中心的消息,敌方已经有一只特种飞蛾避过第二层防卫,直逼内城南端通道入口。但优秀的蜘蛛已经在每个通道内埋下了坚固的大网,无论飞蛾进入哪个通道,他只有死路一条!(因为他是无法挣脱超级蛛网的)
现在,001和002分别驻扎在某两个通道内。各通道通过内线相通,通过每条内线需要一定的时间。当特种飞蛾被困某处,001或002会迅速赶来把它结果掉(当然是耗时最少的那个)。
001跟002都想尽早的完成任务,他们希望选择在最坏情况下能尽早完成任务的方案。
输入描述 Input Description
第一行为一个整数N (N<=100) 表示通道数目。
接下来若干行每行三个正整数a,b,t 表示通道a,b有内线相连,通过的时间为t。(t<=100)
(输入保证每个通道都直接/间接连通)
输出描述 Output Description
两个不同的整数x1,x2,分别为001,002驻扎的地点。(如果有多解,请输出x1最小的方案,x1相同则输出x2最小的方案)
样例输入 Sample Input
3
1 2 5
2 3 10
3 1 3
样例输出 Sample Output
1 2
代码
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 #define INF 0x3f3f3f3f 6 using namespace std; 7 int g[505][505],n; 8 9 void init_(){10 int a,b,t;11 memset(g,-1,sizeof(g));12 scanf("%d",&n);13 while(scanf("%d%d%d",&a,&b,&t)!=EOF){14 g[a][b]=t;15 g[b][a]=t;16 }17 }18 19 void floyd(){20 for(int k=1;k<=n;k++){21 for(int i=1;i<=n;i++){22 if(i!=k){23 for(int j=1;j<=n;j++){24 if(i!=j&&j!=k&&g[i][k]!=-1&&g[k][j]!=-1){25 if(g[i][j]>g[i][k]+g[k][j]||g[i][j]==-1){26 g[i][j]=g[i][k]+g[k][j];27 }28 }29 }30 }31 }32 }33 }34 35 //获得以蜘蛛在a、b两点找到飞蛾的最坏情况(两点各到另一点的距离最小值 的最大值)36 int get_max(int a,int b){37 int temp=0;38 for(int i=1;i<=n;i++){39 int k=min(g[a][i],g[b][i]);40 temp=max(temp,k);41 }42 return temp;43 }44 45 //枚举两个蜘蛛出现的所有可能位置的最坏情况getmax最小值46 void solve(){47 int mn=INF,mi,mj;48 for(int i=1;i<=n;i++){49 for(int j=1;j<=n;j++){50 if(i!=j){51 int temp=get_max(i,j);52 if(temp<mn){53 mi=i;54 mj=j;55 mn=temp;56 }57 }58 }59 }60 printf("%d %d\n",mi,mj);61 }62 63 int main(){64 // freopen("01.in","r",stdin);65 init_();66 floyd();67 solve();68 return 0;69 }转个题解:
在Floyd求出各点间最短路后,还得根据题意枚举一遍两个蜘蛛的出发点,求出两个蜘蛛到它们最远的点(最坏情况)的最快时间,然后输出就OK了,另外要注意下题目描述不清,第一行的n不是指有n条边,而是n个点,后面有 若干行 数据,用while()语句写输入
个人意见,把题目读懂是很重要的
Wikioi 1020 孪生蜘蛛 Label:Floyd最短路
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。