洛谷 [P1119] 灾后重建

我们发现每次询问都是对于任意两点的，所以这是一道多源最短路径的题，多源最短路径，我们首先想到floyd，因为询问的时间是不降的，所以对于每次询问，我们将还没有进行松弛操作的的点k操作。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <algorithm>

#include <cmath>

using namespace std;

const int MAXN=205;

int init(){

	int rv=0,fh=1;

	char c=getchar();

	while(c<'0'||c>'9'){

		if(c=='-') fh=-1;

		c=getchar();

	}

	while(c>='0'&&c<='9'){

		rv=(rv<<1)+(rv<<3)+c-'0';

		c=getchar();

	}

	return rv*fh;

}

int dis[MAXN][MAXN],n,m,t[MAXN],q,p;

inline void floyd(int k){

	for(register int i=1;i<=n;i++){

		for(register int j=1;j<=n;j++){

			dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);

		}

	}

}

int main(){

	freopen("in.txt","r",stdin);

	n=init();m=init();

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

		t[i]=init();

	}

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

		for(int j=1;j<=n;j++){

			dis[i][j]=0x7fffffff/3;

		}

		dis[i][i]=0;

	}

	for(int i=1;i<=m;i++){

		int u=init(),v=init(),di=init();

		dis[u+1][v+1]=di;dis[v+1][u+1]=di;

	}

	q=init();

	for(int i=1;i<=q;i++){

		int x=init(),y=init(),ti=init();

		x++;y++;

		if(t[x]>ti||t[y]>ti) {printf("-1\n");continue;}

		while(t[p+1]<=ti&&(p<=n-1)) floyd(++p);

		if(dis[x][y]==0x7fffffff/3) printf("-1\n");

		else printf("%d\n",dis[x][y]);

	}

	fclose(stdin);

	return 0;

}

巴特西

洛谷 [P1119] 灾后重建

最新文章

热门文章