題目描述

小明喜歡觀景，于是今天他來到了藍橋公園。

已知公園有 N 個景點，景點和景點之間一共有 M?條道路。小明有 Q?個觀景計劃，每個計劃包含一個起點 stst 和一個終點 eded，表示他想從 stst 去到 eded。但是小明的體力有限，對于每個計劃他想走最少的路完成，你可以幫幫他嗎？

輸入描述

輸入第一行包含三個正整數 N,M,Q

第 22 到 M+1行每行包含三個正整數 u,v,w，表示 u?v 之間存在一條距離為 w的路。

第 M+2 到 M+Q?1行每行包含兩個正整數 st,ed，其含義如題所述。

1≤N≤400，1≤M≤N×(N?1)2，Q≤103，1≤u,v,st,ed≤n，1≤w≤109

輸出描述

輸出共 Q?行，對應輸入數據中的查詢。

若無法從 st?到達 ed?則輸出 ?1。

題目分析

? ? ? ? 這是一道關于求最短路徑長度。?

算法：Floyd算法

? ? ? ?關于詳細的學習大家可以參考：弗洛伊德（Floyd）算法求圖的最短路徑_弗洛伊德算法求最短路徑-CSDN博客

核心代碼（不用管路徑，只求最短路勁長度）：

for(int k = 0; k < n; k++) //k是中間點
{for(int v = 0; v < n; v++) //v是起點{for(int w = 0; w < n; w++) //w是終點{D[v][w] = min(D[v][w], D[v][k] + D[k][w]);}}
}

? ? ? ? 使用算法處理后數組D是存放所有點到某點的最短路徑長度。

思路：

（1）先初始化數組D，為了實現判斷，迎合w的值我們將所有值變成2e18(long long 數據類型能夠存儲的最大值)，再將對角線上的值置為0（點自己到自己的距離）。

（2）首先我們將數組D開到足夠大，存儲輸入的路徑長度（注意題目中是雙向的）。

（3）利用算法處理數組中的值。

（4）輸出結果。

代碼

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n, m, q;
ll D[1500][1500];void floyd()
{int k, v, w;for (k = 0; k < n; k++){for (v = 0; v < n; v++){for (w = 0; w < n; w++){D[v][w] = min(D[v][w], D[v][k] + D[k][w]);}}}
}int main()
{cin >> n >> m >> q;ll u, v, w;for(int i = 0; i < n; i++){for(int j = 0; j < n; j++) {D[i][j] = 2e18;}}for(int i = 0; i < n; i++){D[i][i] = 0;}while(m--) {cin >> u >> v >> w;u--;v--;//我們的算法中使用的是0~n-1，所以我們--D[u][v] = D[v][u] = min(w, D[u][v]);}floyd();int st, ed;while(q--) {cin >> st >> ed;st--;ed--;if(D[st][ed] != 2e18){cout << D[st][ed] << "\n";}else{cout << -1 << "\n";}}return 0;
}