【基础练习】【floyd+枚举】codevs1020 孪生蜘蛛题解

墨蓝 2022-08-08 06:15 120阅读 0赞

题目描述 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

简单来说，就是有很多点，点之间有带权边。安放两个蜘蛛在不同位置，使他们到每个点距离的最大值最小。

基本思想是，先用floyd求每对点之间的最短路，然后对于每两个位置i,j枚举，打擂台求出最小值。题目要求i最小，其次j最小，因此只需从小到大枚举即可。

二话不说上代码~

//codevs1020 ÂÏÉúÖ©Öë floyd+Ã¶¾Ù
    //copyright by ametake 
    #include
       
        
    #include
        
         
    #include
         
          
    using namespace std;
    
    int n;
    int f[110][110];
    
    int judge(int &x,int &y)
    {
    	int maxn=-1;
    	for (int k=1;k<=n;k++)
    	{
    		int now=min(f[x][k],f[y][k]);
    		if (maxn

`——相与枕藉乎舟中，不知东方之既白。`

发表评论取消回复

表情：

评论列表（有 0 条评论，120人围观）

还没有评论，来说两句吧...

相关阅读

相关【基础练习】【差分】codevs1242 布局题解

题目描述 Description 当排队等候喂食时，奶牛喜欢和它们的朋友站得靠近些。FJ有N（2<=N<=1000）头奶牛，编号从1到N，沿一条直线站着等候喂食。奶牛排在队伍

青旅半醒/ 2022年08月09日 17:40/ 0 赞/ 168 阅读

相关【基础练习】【Floyd+枚举】codevs1167 树网的核题解

题目描述 Description 【问题描述】设 T=(V, E, W) 是一个无圈且连通的无向图（也称为无根树），每条边带有正整数的权，我们称T 为树网（tre

╰半夏微凉°/ 2022年08月09日 12:46/ 0 赞/ 90 阅读

相关【基础练习】【搜索/枚举】codevs1168 火柴棒等式题解

题目来自NOIP2008 题目描述 Description 给你n根火柴棍，你可以拼出多少个形如“A+B=C”的等式？等式中的A、B、C是用火柴棍拼出的整数（若该数非零，则

Dear 丶/ 2022年08月09日 09:41/ 0 赞/ 138 阅读

相关【基础练习】【模拟】codevs1704 卡片游戏题解

题目描述 Description 桌面上有一叠牌，从第一张牌(即位于顶面的牌)开始从上往下依次编号为1~n.当至少还剩两张排时进行一下操作：把第一张牌扔掉，然后把新的第一张牌

川长思鸟来/ 2022年08月09日 02:21/ 0 赞/ 203 阅读

相关【基础练习】【栈】codevs2058 括号匹配题解

这道题目就不多说了非常经典的栈练习左括号压栈，右括号比较布尔变量判断即可曾经写过一到类似的表达式求值博客上有可以参考这道题目的最后一个点非常坑不知道哪里

朱雀/ 2022年08月08日 06:57/ 0 赞/ 169 阅读

相关【基础练习】【floyd+枚举】codevs1020 孪生蜘蛛题解

题目描述 Description 在G城保卫战中，超级孪生蜘蛛Phantom001和Phantom002作为第三层防卫被派往守护内城南端一带极为隐秘的通道。根据防护中心的

墨蓝/ 2022年08月08日 06:15/ 0 赞/ 121 阅读

相关【基础练习】【贪心】codevs1214 线段覆盖题解

题目：已知数轴上0<N<10000条线段。每条线段按照端点Ai和Bi（Ai<>Bi,i=1..N）定义。端点坐标在（-999，999）内，坐标为整数。有些线段可能相交。编程实现

偏执的太偏执、/ 2022年08月07日 09:41/ 0 赞/ 176 阅读

相关【基础练习】【枚举/搜索】codevs1792 分解质因数题解

题目描述 Description 编写一个把整数N分解为质因数乘积的程序。输入描述 Input Description 输入一个整数 N 输出描述 Output De

电玩女神/ 2022年08月04日 08:27/ 0 赞/ 122 阅读

相关【基础练习】【堆】codevs1063 合并果子题解

是的我受不了诸城一中的魔鬼DEVCPP了还有魔鬼codeblocks 每次编译都要把六个文件都点一遍删除可执行文件再重新编译= =命令行也各种问题受不了他直接

￡神魔★判官ぃ/ 2022年08月02日 15:53/ 0 赞/ 187 阅读

相关 1020 孪生蜘蛛

题目描述 Description 在G城保卫战中，超级孪生蜘蛛Phantom001和Phantom002作为第三层防卫被派往守护内城南端一带极为隐秘的通道。根据防护中心的

Love The Way You Lie/ 2022年06月16日 08:42/ 0 赞/ 159 阅读