洛谷 P1119 灾后重建

关于Floyd:它活了

?
?
详细题面戳此处

?
?

自从上次nodgd的毒瘤卡常之后好久没做到必须要用Floyd来跑的题了
此题最开始的思路是每个询问更新点距然后一个询问跑一次\(Dij\)。但稍微算一下时间复杂度发现会爆。
再细读一下，发现每一次更新点之后只有最短路与更新点有关的点的距离会更新。
于是马上想到\(Floyd\)。每次更新点的时候顺便把以它为转移点的最短路处理了，期望复杂度\(O(N^3)\),常数可能较大。
这道题可以加深与我一样初学\(OI\)的萌新对\(Floyd\)本质的理解。真是一道好题啊！
?

注：讲\(Dij\)时老板的啪啪忒上说堆优化后的复杂度为\(O(Nlog(N))\)，但实际上复杂度是\(O(Mlog(M))\)，所以在边数巨大，点数较小时推荐使用\(Floyd\)老板啪啪忒害人不浅啊
老板啪啪忒你也敢信？

KONO代码哒！

//关于Floyd：他活了
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
typedef long long ll;
const ll maxn=210;
const ll inf=0x3f3f3f3f3f3f3f3f;
struct node{
    ll id,t;
}p[maxn];
bool cmp(node a,node b)
{
    return a.t<b.t;
}
ll dis[maxn][maxn];
bool able[maxn];
ll n,m,q;
ll x,y,t;
int main()
{
    memset(dis,0x3f,sizeof(dis));
    scanf("%lld%lld",&n,&m);
    ll i,j,k;
    for(i=0;i<n;i++)
    {
        scanf("%lld",&p[i].t);
        p[i].id=i;
        dis[i][i]=0;
    }
    for(i=1;i<=m;i++)
    {
        ll a,b,c;
        scanf("%lld%lld%lld",&a,&b,&c);
        dis[a][b]=min(dis[a][b],c);
        dis[b][a]=min(dis[b][a],c);
    }
    sort(p,p+n,cmp);
    scanf("%lld",&q);
    j=0;
    while(q--)
    {
        scanf("%lld%lld%lld",&x,&y,&t);
        while(p[j].t<=t&&j<=n){
            ll u=p[j].id;
            able[u]=1;
            for(i=0;i<n;i++)
            {
                for(ll k=0;k<n;k++){
                    if(dis[i][u]+dis[u][k]<dis[i][k])
                    {
                        dis[i][k]=dis[i][u]+dis[u][k];
                    }
                }
            }
            j++;
        }
        if(!able[x]||!able[y])printf("-1\n");
        else
        if(dis[x][y]!=inf){
            printf("%lld\n",dis[x][y]);
        }
        else printf("-1\n");
    }
    return 0;
}

新桌面GET!

洛谷P1119 灾后重建

原文：https://www.cnblogs.com/cooper233/p/11886495.html