*P1119 灾后重建[floyd]

题目背景

BB地区在地震过后，所有村庄都造成了一定的损毁，而这场地震却没对公路造成什么影响。但是在村庄重建好之前，所有与未重建完成的村庄的公路均无法通车。换句话说，只有连接着两个重建完成的村庄的公路才能通车，只能到达重建完成的村庄。

题目描述

给出BB地区的村庄数NN，村庄编号从00到N-1N?1，和所有MM条公路的长度，公路是双向的。并给出第ii个村庄重建完成的时间t_iti，你可以认为是同时开始重建并在第t_iti天重建完成，并且在当天即可通车。若t_i*t**i为00则说明地震未对此地区造成损坏，一开始就可以通车。之后有QQ个询问(x, y, t)(x,y,t)，对于每个询问你要回答在第tt天，从村庄xx到村庄y的最短路径长度为多少。如果无法找到从xx村庄到yy村庄的路径，经过若干个已重建完成的村庄，或者村庄xx或村庄yy*在第t天仍未重建完成 ，则需要返回-1?1。

解析

有毒。打完dij交上去T掉才后知后觉，这题得用floyd。

首先，容易得出dij复杂度\(O(Q(n+m)log~n)\)，对于\(m\)较大的这道题来说，达到了\(1e9\)级别，显然会炸，再吸氧也过不了。

先把T掉4个点的dij贴上来：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<queue>
#include<vector>
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define N 201
#define M 10010
#define MOD 2520
#define E 1e-12
#define ri register int
using namespace std;
//start from 0
inline int read()
{
    int f=1,x=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
struct rec{
    int next,ver,edge;
}g[M<<1];
int head[N],tot,n,m,d[N],t[M];
bool v[N],ve[M<<1];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
inline void add(int x,int y,int val)
{
    g[++tot].ver=y,g[tot].edge=val;
    g[tot].next=head[x],head[x]=tot;
}
inline void dij(int x)
{
    memset(v,0,sizeof(v));
    memset(d,0x3f,sizeof(d));
    d[x]=0;q.push(make_pair(0,x));
    while(q.size()){
        int index=q.top().second;q.pop();
        if(v[index]||!ve[index]) continue;
        v[index]=1;
        for(ri i=head[index];i;i=g[i].next){
            int y=g[i].ver,z=g[i].edge;
            if(d[y]>d[index]+z&&ve[y]){
                d[y]=d[index]+z;
                q.push(make_pair(d[y],y));
            }
        }
    }
}
int main()
{
    n=read(),m=read();
    for(int i=0;i<n;++i) t[i]=read();
    t[n]=INF;
    for(ri i=1;i<=m;++i){
        int u,v,val;
        u=read(),v=read(),val=read();
        add(u,v,val),add(v,u,val);
    }
    int q,nowc=0;
    q=read();
    while(q--){
        int u,v,ti;
        u=read(),v=read(),ti=read();
        while(t[nowc]<=ti) ve[nowc]=1,nowc++;
        dij(u);
        if(d[v]==INF) printf("-1\n");
        else printf("%d\n",d[v]);
    }
    return 0;   
} 

然后讲讲正解：

首先一看题目要求每次两点之间最短路，想到floyd，但是你兢兢业业地跑个\(Q\)次复杂度就到了\(O(n^4)\)，结果甚至不如dij。

如果深入理解了floyd的工作原理，会知道它是按照dp的思路每次对任意两点，找另一个不同于这两点的中间点去更新最短距离。仔细观察发现，在这题中，每秒最多增加一个点，我们不妨在每次加入这个点时，就拿这个新点当作中间点去更新最短路，显然跟原版floyd是没有区别的。

这样一来，复杂度就被降到了\(O(n^3)\)，级别最大大概只有\(1e7\)，卡卡常是可以顺利通过本题的。

吸氧，卡常之后，效率还是比较可观的：

\(85ms,916kb\)，甚至排到了最优解的第二页。。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<queue>
#include<vector>
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define N 201
#define M 10010
#define MOD 2520
#define E 1e-12
#define ri register int
using namespace std;
//start from 0
inline int read()
{
    int f=1,x=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int g[N][N],n,m,t[M];
inline void fly(int k)
{
    for(int i=0;i<n;++i)
        for(int j=0;j<n;++j)
            g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
}
int main()
{
    n=read(),m=read();
    for(int i=0;i<n;++i) t[i]=read();
    t[n]=INF;
    for(int i=0;i<n;++i)
        for(int j=0;j<n;++j) g[i][j]=INF;
    for(int i=0;i<n;++i) g[i][i]=0;
    for(ri i=1;i<=m;++i){
        int u,v,val;
        u=read(),v=read(),val=read();
        g[u][v]=g[v][u]=val;
    }
    int q,nowc=0;
    q=read();
    for(int i=1;i<=q;++i){
        int u,v,ti;
        u=read(),v=read(),ti=read();
        while(t[nowc]<=ti) fly(nowc),nowc++;
        if(t[u]>ti||t[v]>ti) printf("-1\n");
        else if(g[u][v]==INF) printf("-1\n");
        else printf("%d\n",g[u][v]);
    }
    return 0;   
} 

*P1119 灾后重建[floyd]

原文：https://www.cnblogs.com/DarkValkyrie/p/11402386.html