P1119 灾后重建Floyd

输入输出样例
输入 #1复制
4 5
1 2 3 4
0 2 1
2 3 1
3 1 2
2 1 4
0 3 5
4
2 0 2
0 1 2
0 1 3
0 1 4
输出 #1复制
-1
-1
5
4

Floyd应用
可以求出两点之间最短路
处理on3

//基本模板
for(int k=1;k<=n;k++)for(int i=1;i<=n;i++）for(int j=1;j<=n;j++)f[i][j]=min(f[i][k]+f[k][j],f[i][k])

本题是在操作的过程中建立联系由于每个村重建时间不一所以不可以提前建立联系比较好的是 他们重建的时间是递增的所以不会出现多建立联系的情况

void updata(int k){
    for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(Floyd[i][j]>Floyd[i][k]+Floyd[j][k]) //前任复合 现任必输！！！ 更新更新Floyd[i][j]=Floyd[j][i]=min(Floyd[i][j],Floyd[i][k]+Floyd[j][k])
//应该
while(day[now]<=w&&now<n){
     //把这个时间之前的村庄建立联系updata(now);now++;}
}
//而不是 
for(int i=1;i<=n;i++)  updata(i); //不要一股脑直接建立完 然后判断day

**

问题

**
code

#include<bits/stdc++.h>
#include<iostream>
#include<cstring>
#include<queue>
#define inf 0x3f3f3f3f
//2147483647
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
ll n,m,k;
ll cnt=0;
ll mod=80112002;
const int maxn=1e6+199;struct node{
    int u,v,w,next;
}e[maxn];
int head[maxn]; 
ll dis[maxn]; // ju
int vis[maxn]; // dll Floyd[300][300];
int day[maxn];
void updata(int k){
    for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(Floyd[i][j]>Floyd[i][k]+Floyd[j][k])Floyd[i][j]=Floyd[j][i]=min(Floyd[i][j],Floyd[i][k]+Floyd[j][k]);
}
int main(){
    cin>>n>>m;for(int i=0;i<n;i++){
    cin>>day[i];}for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
    if(i==j)Floyd[i][j]=0;elseFloyd[i][j]=Floyd[j][i]=inf;}}int now=0;for(int i=1;i<=m;i++){
    int u,v,w;cin>>u>>v>>w;Floyd[u][v]=Floyd[v][u]=w;}cin>>k;for(int i=1;i<=k;i++){
    int u,v,w;cin>>u>>v>>w;while(day[now]<=w&&now<n){
    updata(now);now++;}if(Floyd[u][v]==inf||day[u]>w||day[v]>w){
    cout<<-1<<endl;}else{
    cout<<Floyd[u][v]<<endl;}}return 0;
}