带鼠的动物浙江大学哈利·波特要考试了，他需要你的帮助

时间：2024-04-30 14:08:57 作者：好再定算命网来源：原创

单位浙江大学

哈利·波特要参加考试，他需要你的帮助。本课程教您使用魔法将一种动物变成另一种动物的能力。例如，把猫变成老鼠的咒语是“哈哈”，把老鼠变成鱼的咒语是“呵呵”，等等。反方向改变咒语就是简单地反向念诵原来的咒语，例如啊哈可以把老鼠变成猫。另外，如果想把猫变成鱼带鼠的动物浙江大学哈利·波特要考试了，他需要你的帮助，可以直接念咒语，也可以把猫变成老鼠、老鼠变成鱼的咒语组合起来：。

现在哈利·波特手里有一本教科书，上面列出了所有的变形咒语和可以改变的动物。老师允许他带一只动物到考场，测试他将动物变成任意指定动物的能力。于是他就来问你：你能带什么动物，能让最难变的动物（也就是需要最长咒语的动物变成哈利·波特自己带来的动物）需要最短的咒语？例如：如果只有猫、老鼠和鱼，那么显然哈利·波特应该带上老鼠，因为老鼠只需要念出4个字就可以变成另外两种动物；如果他带了猫，他需要发音至少6个字符。只有人物才能把猫变成鱼；同样，带鱼也不是最好的选择。

输入格式：

输入指令：输入第1行给出两个正整数N（≤100）和M，其中N为参与测试的动物总数好再定运势网，M为直接变换所用的魔棒数量。为了简单起见，我们将动物从1到N编号。然后有M行，每行给出3个正整数，分别是两只动物的编号和它们变形所需的咒语长度（≤100）。数字之间用空格分隔。

输出格式：

输出哈利·波特应该带进考场的动物数量，以及最长的变形咒的长度，以空格分隔。如果仅用一只动物无法完成所有变换要求，则输出0。如果可以选择的动物有多种，则输出数量最小的一种。

输入示例：

输出样本：

4 70

个人想法：

这是一个多源最短路径问题。适合用Floyd算法来求解。

我们首先使用邻接矩阵来存储每两个动物之间的变换咒语的长度，然后使用Floyd算法获得从每个动物到其他动物的咒语长度。当它们不可变时，我们需要输出0；

为了找到合适的动物带鼠的动物，我们需要遍历行。每行代表从一种动物到其他动物的咒语长度。遍历每一行，保存该行的最大值。如果有不可达，则直接返回。无法触及该动物。遍历完每一行后，我们需要更新每一行中最大值中的最小值，并保存对应的行，即我们要带的动物，以及法术的长度。

交流代码：

#include 
#include 
#include 
using namespace std;
const int N = 210, INF = 1e9;
int n, m, Q;
int d[N][N];
void floyd()
{
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i == j) d[i][j] = 0;
            else d[i][j] = INF;
    while (m--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        d[a][b] = min(d[a][b], c);
        d[b][a] = min(d[b][a], c);
    }
    floyd();
    int Maxn = 0,Maxpre=100000,max;
    int i=1, j=1;
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            if (i != j) {
                if (d[i][j] == INF) {
                    Maxn = 0;
                    break;
                }
                else if (d[i][j] > Maxn) {
                    Maxn = d[i][j];
                }
            }
        }
        if (Maxn != 0) {
            if (Maxn < Maxpre) {
                Maxpre = Maxn;
                max = i;
            }
        }
        Maxn = 0;
    }
    if (Maxpre == 100000) {
        cout << "0";
        return 0;
    }
    cout << max << " " << Maxpre;
    return 0;
}