题目描述
小明喜欢观景，于是今天他来到了蓝桥公园。已知公园有 N 个景点，景点和景点之间一共有 M 条道路。小明有 Q 个观景计划，每个计划包含一个起点 st 和一个终点 ed，表示他想从 st 去到 ed。但是小明的体力有限，对于每个计划他想走最少的路完成，你可以帮帮他吗？
输入描述
输入第一行包含三个正整数N,M,Q第 2 到M+1 行每行包含三个正整数 u,v,w，表示 u↔v 之间存在一条距离为 w 的路。
第 M+2 到 M+Q−1 行每行包含两个正整数 st,ed，其含义如题所述。
1\leq N\leq 4001≤N≤400，1\leq M \leq \dfrac{N\times(N - 1)}{2}1≤M≤2N×(N−1)，Q\leq 10^3Q≤103，1\leq u,v,st,ed \leq n1≤u,v,st,ed≤n，1\leq w \leq 10^91≤w≤109
输出描述
输出共 Q 行，对应输入数据中的查询。若无法从 st 到达 ed 则输出 −1。
输入输出样例
示例 1输入
3 3 3
1 2 1
1 3 5
2 3 2
1 2
1 3
2 3
输出1
3
2
这道题很明显是Floyd的模板题，但是我被坑了很多次：
1.题目的st跟ed可能是同一个点，这时距离就为0
2.在初始化dis数组时，我定义了最大值N=1e9+10，但是还不够大，因为题目中w最大是1e9，那可能就有两个点的w相加大于N，这时候判断该两点有无路径就会出错
3.输入的两个点的直接路径可能不只有一个，这时候就要取最小值
4.Floyd函数中k也就是拓展用的点，要在最外层循环，可以试想一下，如果k在最里层，则每个点就只能遍历一次，也就是只有一次机会被拓展，这显然很不合理
代码如下：
#include<bits/stdc++.h>
using namespace std;
long long dis[1010][1010];
const long long maxN=1e9+10;
void floyd(int n) {
for(int k=1; k<=n; k++) {
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
}
}
int main() {
int n,m,q;
cin>>n>>m>>q;
for(int i=0; i<=n; i++) {
for(int j=0; j<=n; j++) {
dis[i][j]=maxN;
if(i==j)dis[i][j]=0;
}
}
cout<<maxN<<endl;
for(int i=0; i<m; i++) {
long long u,v,w;
cin>>u>>v>>w;
dis[u][v]=min(dis[u][v],w);
dis[v][u]=min(dis[v][u],w);
}
floyd(n);
while(q--) {
int st,ed;
cin>>st>>ed;
if(dis[st][ed]>=maxN)cout<<-1<<endl;
else cout<<dis[st][ed]<<endl;
}
return 0;
}
