洛谷P1119 灾后重建 Floyd + 离线

https://www.luogu.org/problemnew/show/P1119

真是有故事的一题呢

半年前在宁夏做过一道类似的题，当时因为我的愚昧痛失了金牌。

要是现在去肯定稳稳的过，真是生不逢时。

简单的来说就是按照时间顺序一边建边一边查询，对于每次建边只要用floyd加中转点即可。

#include <map>

#include <set>

#include <ctime>

#include <cmath>

#include <queue>

#include <stack>

#include <vector>

#include <string>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <sstream>

#include <iostream>

#include <algorithm>

#include <functional>

using namespace std;

inline int read(){int now=;register char c=getchar();for(;!isdigit(c);c=getchar());

for(;isdigit(c);now=now*+c-'',c=getchar());return now;}

#define For(i, x, y) for(int i=x;i<=y;i++)

#define _For(i, x, y) for(int i=x;i>=y;i--)

#define Mem(f, x) memset(f,x,sizeof(f))

#define Sca(x) scanf("%d", &x)

#define Sca2(x,y) scanf("%d%d",&x,&y)

#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)

#define Scl(x) scanf("%lld",&x);

#define Pri(x) printf("%d\n", x)

#define Prl(x) printf("%lld\n",x);

#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();

#define LL long long

#define ULL unsigned long long

#define mp make_pair

#define PII pair<int,int>

#define PIL pair<int,long long>

#define PLL pair<long long,long long>

#define pb push_back

#define fi first

#define se second

typedef vector<int> VI;

const double eps = 1e-;

const int maxn = ;

const int INF = 0x3f3f3f3f;

const int mod = 1e9 + ;

const int maxm = 5e4 + ;

int N,M,Q;

pair<int,int>P[maxn];

int dp[maxn][maxn];

struct Query{

    int x,y,t;

}query[maxm];

bool vis[maxn];

bool cmp(Query a,Query b){

    return a.t < b.t;

}

void add(int x){

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

        if(i == x) continue;

        for(int j = ; j < N ; j ++){

            if(j == x) continue;

            dp[i][j] = min(dp[i][j],dp[i][x] + dp[x][j]);

        }

    }

}

int main(){

    //freopen("C.in", "r", stdin);

    Sca2(N,M);

    for(int i = ; i <= N -  ; i ++){

        Sca(P[i].first);

        P[i].second = i;

    }

    Mem(dp,0x3f);

    for(int i = ; i <= N - ; i ++) dp[i][i] = ;

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

        int u,v,w; Sca3(u,v,w);

        dp[u][v] = dp[v][u] = w;

    }

    sort(P ,P + N);

    Sca(Q);

    int now = ,cnt = ;

    while(cnt < N && P[cnt].first == ){

        vis[cnt] = ;

        add(P[cnt++].second);

    }

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

        Sca3(query[i].x,query[i].y,query[i].t);

        while(cnt < N && P[cnt].first <= query[i].t){

            vis[cnt] = ;

            add(P[cnt++].second);

        }

        if(!vis[query[i].x] || !vis[query[i].y] || dp[query[i].x][query[i].y] == INF) Pri(-);

        else Pri(dp[query[i].x][query[i].y]);

    }

    return ;

}

秒客网

洛谷P1119 灾后重建 Floyd + 离线

相关文章