哈利波特的變形課考試

哈利·波特的考試   (25分)

哈利·波特要考試了，他需要你的幫助。這門課學的是用魔咒将一種動物變成另一種動物的本事。

例如将貓變成老鼠的魔咒是haha，将老鼠變成魚的魔咒是hehe等等

。反方向變化的魔咒就是簡單地将原來的魔咒倒過來念，例如ahah可以将老鼠變成貓。

另外，如果想把貓變成魚，可以通過念一個直接魔咒lalala，

也可以将貓變老鼠、老鼠變魚的魔咒連起來念：hahahehe。

現在哈利·波特的手裡有一本教材，裡面列出了所有的變形魔咒和能變的動物。

老師允許他自己帶一隻動物去考場，要考察他把這隻動物變成任意一隻指定動物的本事。

于是他來問你：帶什麼動物去可以讓最難變的那種動物

（即該動物變為哈利·波特自己帶去的動物所需要的魔咒最長）

需要的魔咒最短？

例如：如果隻有貓、鼠、魚，則顯然哈利·波特應該帶鼠去

，因為鼠變成另外兩種動物都隻需要念4個字元；

而如果帶貓去，則至少需要念6個字元才能把貓變成魚；同理，帶魚去也不是最好的選擇。

輸入格式:

輸入說明：輸入第1行給出兩個正整數NNN

(≤100\le 100≤100)和MMM，其中NNN是考試涉及的動物總數，

MMM是用于直接變形的魔咒條數。為簡單起見，我們将動物按1~NNN編号。

随後MMM行，每行給出了3個正整數，分别是兩種動物的編号、

以及它們之間變形需要的魔咒的長度(≤100\le 100≤100)，數字之間用空格分隔。

輸出格式:

輸出哈利·波特應該帶去考場的動物的編号、以及最長的變形魔咒的長度，中間以空格分隔。

如果隻帶1隻動物是不可能完成所有變形要求的，則輸出0。如果有若幹隻動物都可以備選，則輸出編号最小的那隻。

輸入樣例:

6 11

3 4 70

1 2 1

5 4 50

2 6 50

5 6 60

1 3 70

4 6 60

3 6 80

5 1 100

2 4 60

5 2 80

輸出樣例:

4 70

解題思路：

首先保證是 圖 是連通的，不存在孤立點

其次 搜尋起點不同 的 每個圖 最長的 最短路徑

然後輸出所有最長 的 最短 路徑中的最短

= =繞了下~

要求多點 是以這裡用floyd ，四行動歸特簡單.....

#include <iostream>
#include<memory.h>
using namespace std;

int main()
{
    const int INF = 0x3f3f3f3f,MAXNUM = 101;
    int g[MAXNUM][MAXNUM];
//輸入和初始化
    int nnn,mmm;
    cin>>nnn>>mmm;
    memset(g,INF,sizeof(g));

    for(int i=1;i<=mmm;++i)
    {
        int num1,num2,len;
        cin>>num1>>num2>>len;
        g[num1][num2] = len;
        g[num2][num1] = len;
    }

    for(int i=1;i<=nnn;++i){
        for(int j=1;j<=nnn;++j){
            if(i==j){//對角線去掉
                g[i][j] = 0;
            }
        }
    }

    for(int k=1;k<=nnn;++k)
        for(int i=1;i<=nnn;++i)
            for(int j=1;j<=nnn;++j){
                g[i][j] = min(g[i][j],g[i][k]+g[k][j]);
            }//核心算法
    int flag = 0;
    int num = INF;
    int mindis = INF;
    //處理下輸出資料
    for(int i=1;i<=nnn;++i)
    {
        int maxdis = -1;
        for(int j=1;j<=nnn;++j)
        {
            if(g[i][j]==INF){
                flag = 1;
                break;
            }else{
                maxdis = max(g[i][j],maxdis);
            }
        }
        if(flag == 1){
            break;
        }
        if(mindis>maxdis){
            mindis = maxdis;
            num = i;
        }
    }
//分下類輸出
    if(flag == 1){
        cout<<0<<endl;
    }else{
        cout<<num<<" "<<mindis<<endl;
    }

    return 0;
}