一：題目：

哈利·波特要考試了，他需要你的幫助。這門課學的是用魔咒將一種動物變成另一種動物的本事。例如將貓變成老鼠的魔咒是haha，將老鼠變成魚的魔咒是hehe等等。反方向變化的魔咒就是簡單地將原來的魔咒倒過來念，例如ahah可以將老鼠變成貓。另外，如果想把貓變成魚，可以通過念一個直接魔咒lalala，也可以將貓變老鼠、老鼠變魚的魔咒連起來念：hahahehe。

現在哈利·波特的手里有一本教材，里面列出了所有的變形魔咒和能變的動物。老師允許他自己帶一只動物去考場，要考察他把這只動物變成任意一只指定動物的本事。于是他來問你：帶什么動物去可以讓最難變的那種動物（即該動物變為哈利·波特自己帶去的動物所需要的魔咒最長）需要的魔咒最短？例如：如果只有貓、鼠、魚，則顯然哈利·波特應該帶鼠去，因為鼠變成另外兩種動物都只需要念4個字符；而如果帶貓去，則至少需要念6個字符才能把貓變成魚；同理，帶魚去也不是最好的選擇。

輸入格式:
輸入說明：輸入第1行給出兩個正整數N (≤100)和M，其中N是考試涉及的動物總數，M是用于直接變形的魔咒條數。為簡單起見，我們將動物按1~N編號。隨后M行，每行給出了3個正整數，分別是兩種動物的編號、以及它們之間變形需要的魔咒的長度(≤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

二：思路分析：

多源點最短路徑，分析題目時，如果不知從何下手 可以從數據入手 分析數據特征 比自己干推 要省點時間

三：上碼

//分析輸出 0 時 那是說明圖是不連通的 統計結點個數 不夠N則輸出0 （只帶1只動物是不可能完成所有變形要求的）； // 多源點最短路徑問題 ，從數據分析來看 帶4在去則 最長的路徑長度也就是 70，那么的話 如果我選擇1的話 那么 在他這個最短路徑當中，最長的是 100 ，那么也就是說 //求出所有點 當中最長的那個路徑長度進行比較，選擇最小的那個即是要選擇的結點 。如果有相同最小長度的結點 那么選擇其中編號 最小的 #include<bits/stdc++.h> using namespace std; #define infinite 99999int N,M; int cnt;//記錄訪問結點的個數 typedef struct Graph* PtrGraph; typedef struct Graph {int Ne;int Nv;int Data[101][101]; }graph;void creatGraph(PtrGraph G) {int i,j,w;cin >> N >> M;G->Nv = N;G->Ne = M;for(int i = 1; i <= G->Nv; i++){for(int j = 1; j <= G->Nv; j++){G->Data[i][j] = infinite;//初始化 設置為無窮大 方便沒有鏈接的點表示距離if(i == j)G->Data[i][j] = 0; }}for(int k = 0; k < G->Ne; k++){cin >> i >> j >> w;G->Data[i][j] = w;G->Data[j][i] = w;} } //每次將其中的 最大值 返回 int dijkstra(PtrGraph G,int a,int vis[]) {int dist[101] = {0};int max = 0;vis[a] = 1;cnt++;for(int i = 1; i <= G->Nv; i++){dist[i] = G->Data[a][i];}while(1)//將剩余的結點 進行多次求最小值；{ int m = -1;int min = infinite;for(int i = 1; i <= G->Nv; i++){if(dist[i] < min && vis[i] != 1){min = dist[i];m = i;}}if(m == -1)break;//證明已經沒有最小的權值了 vis[m] = 1;//記錄已經訪問過的cnt++;//記錄訪問的結點個數for(int i = 1; i <= G->Nv; i++){if( vis[i] != 1 && G->Data[m][i] + min < dist[i]){dist[i] = G->Data[m][i] + min;}}}for(int i = 1; i <= G->Nv; i++){//cout << dist[i] << ' ';if(dist[i] > max){max = dist[i]; // cout << dist[i] << ' ';}}return max;} int main() {PtrGraph G;int flag = 0;vector<int>v;int min = 1000,array[101],k = 1;G = (PtrGraph)malloc(sizeof(struct Graph));creatGraph(G);int a = 1;v.push_back(a);//vector容器的下標 是從0開始 我們想要的是從1開始for(int i = 1; i <= G->Nv && flag ==0; i++){cnt = 0;int visited[101] = {0};int temp = dijkstra(G,i,visited);array[k++] = temp;v.push_back(temp);//這里vector容器的下標 是從1開始if(cnt != N){flag = 1;}}if( flag == 1)cout << "0" << endl;else{sort(v.begin()+1,v.end());for(int i = 1; i <= k; i++){if(array[i] == v[1]){if( i < min )min = i;}}cout << min << ' ' << v[1] << endl;}}

總結

以上是生活随笔為你收集整理的7-8 哈利·波特的考试 (25 分)（详解+思路分析）真香啊的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。