洛谷 P1119 灾后重建——dijstra

先上一波题目 https://www.luogu.org/problem/P1119

这道题我们可以将询问按时间排序 然后随着询问将相应已经重建成功的点进行操作

每次更新一个点就以他为起点跑一遍dijstra

当然这样还远远不够 因为新加入一个点可能影响到另外两个点之间的最短路

所以我们跑完dijstra之后还需要n方枚举两个点 看看他们是否能通过这个点更新最短路

这样做的复杂度 每次更新一个点复杂度是 n^2+mlogn 所以整体最差复杂度是 n^3logn

题目n最大为200 明显复杂度是合理的 实际测评跑起来也是飞快

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#include<cmath>

using namespace std;

const int M=,inf=1e9+;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,Q,wh[M];

struct node{int to,next,w;}e[M*M];

int first[M],cnt;

void ins(int x,int y,int w){e[++cnt]=(node){y,first[x],w}; first[x]=cnt;}

int dis[M][M],in[M],ans[M*M];

struct qaq{int x,y,id,T;}s[M*M];

int cmp(qaq x,qaq y){return x.T<y.T;}

struct qwq{

    int id,d;

    bool operator<(const qwq&x)const{return x.d<d;}

};

priority_queue<qwq>q;

void dj(int S){

    in[S]=; dis[S][S]=;

    q.push((qwq){S,dis[S][S]});

    while(!q.empty()){

        qwq x=q.top(); q.pop();

        if(dis[S][x.id]<x.d) continue;

        for(int i=first[x.id];i;i=e[i].next){

            int now=e[i].to;

            if(!in[now]) continue;

            if(dis[S][now]>dis[S][x.id]+e[i].w){

                dis[S][now]=dis[S][x.id]+e[i].w;

                q.push((qwq){now,dis[S][now]});

            }

        }

    }

    for(int i=;i<=n;i++)if(in[i]) dis[i][S]=dis[S][i];

    for(int i=;i<=n;i++)if(in[i])

        for(int j=;j<=n;j++)if(in[j])

            if(dis[i][j]>dis[i][S]+dis[S][j]) dis[i][j]=dis[i][S]+dis[S][j];

}

int main(){

    int x,y,w,now=;

    n=read(); m=read();

    for(int i=;i<=n;i++)

    for(int j=;j<=n;j++)if(i!=j) dis[i][j]=inf;

    for(int i=;i<=n;i++) wh[i]=read(),in[i]=;

    for(int i=;i<=m;i++) x=read()+,y=read()+,w=read(),ins(x,y,w),ins(y,x,w);

    Q=read();

    for(int i=;i<=Q;i++) s[i].x=read()+,s[i].y=read()+,s[i].T=read(),s[i].id=i;

    sort(s+,s++Q,cmp);

    for(int i=;i<=Q;i++){

        while(now<=n&&wh[now]<=s[i].T) dj(now),now++;

        if((!in[s[i].x])||(!in[s[i].y])||(dis[s[i].x][s[i].y]==inf)) ans[s[i].id]=-;

        else ans[s[i].id]=dis[s[i].x][s[i].y];

    }

    for(int i=;i<=Q;i++) printf("%d\n",ans[i]);

    return ;

}