P1119 灾后重建（Floyd的妙用）

luogu P1119 灾后重建
这道题考的是Floyd的妙用，也可以说是对Floyd内涵的考察
总所周知，Floyd是一个复杂度为 $O(n^3)$的算法，也就是说在限时 $1s$的情况下数据非常弱才会用到他
但是该算法的dp思想正是解题的关键
每当需要更新距离的时候，只需拿出用来充当松弛操作中转点的结点，进行一次松弛操作
就维护了一次最小距离
当然在这道题中要注意，当两节点直接相连时，还需特判是否已修建完成

#include<bits/stdc++.h>
using namespace std;int a[205];
int dp[205][205];
int inf=0x3f3f3f3f;
int n,m;void fld(int k)
{for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(i==j) continue;dp[i][j]=min(dp[i][j],dp[i][k]+dp[j][k]);}}
}int main()
{scanf("%d%d",&n,&m);for(int i=0;i<n;i++)scanf("%d",&a[i]);memset(dp,0x3f,sizeof(dp));for(int i=1;i<=m;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);dp[u][v]=dp[v][u]=w;}for(int i=0;i<n;i++)dp[i][i]=0;int q;scanf("%d",&q);int top=0;for(int i=1;i<=q;i++){int u,v,t;scanf("%d%d%d",&u,&v,&t);while(top<n&&a[top]<=t){fld(top);top++;}if(a[u]>t||a[v]>t||dp[u][v]==inf) printf("-1\n");///特判操作elseprintf("%d\n",dp[u][v]);}return 0;
}