5. 蓝桥公园

题目描述

小明喜欢观景，于是今天他来到了蓝桥公园。

已知公园有 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;
}