洛谷P1119 灾后重建 Floyd + 按时间更新

文章来自  Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

题解

保证t是不下降的,这个条件很有意思啊……

n<=1000,还是稠密图,Floyd稳稳的……

不过我们在做这道题的时候,发现这道题能不能通车其实还跟时间有关系,这就比较有趣了。

我们观察Floyd的计算式:

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

不难发现这计算式其实只是跟中间的k有关系,而0——N-1号城市的更新时间又是非递减的,所以我们只需要按照询问时间不断加入新点更新两点间距离就可以了。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 205;
int t[maxn];
int mp[maxn][maxn];
int ans = 0;
int n,m,q;
int cur = -1;
const int INF = 1e9;
void update(int k){
	for(int i = 0;i < n;++i)
		for(int j = 0;j < n;++j)
			mp[i][j] = min(mp[i][j],mp[i][k] + mp[k][j]);
	return;
}
int get_num(){
	int num = 0;
	char c;
	bool flag = false;
	while((c = getchar()) == ' ' || c == '\r' || c == '\n');
	if(c == '-')
		flag = true;
	else num = c - '0';
	while(isdigit(c = getchar()))
		num = (num<<1) + (num << 3) + c - '0';
	return (flag ? -1 : 1) * num;
}
int x,y,z;
int main(){
	n = get_num();
	m = get_num();
	for(int i = 0;i < n;++i){
		t[i] = get_num();
	}
	for(int i = 0;i < n;++i){
		for(int j = 0;j < i;++j)
			mp[i][j] = mp[j][i] = INF;
	}
	for(int i = 1;i <= m;++i){
		x = get_num();
		y = get_num();
		z = get_num();
		mp[x][y] = mp[y][x] = z;
	}
	q = get_num();
	for(int i = 1;i <= q;++i){
		x = get_num();
		y = get_num();
		z = get_num();
		while(t[cur+1] <= z && cur+1 < n){
			cur++;
			update(cur);
		}
		if(t[x] > z || t[y] > z || mp[x][y] == INF)printf("-1\n");
		else printf("%d\n",mp[x][y]);
	}
	return 0;
}


Sign in to leave a comment.
No Leanote account ? Sign up now.
0 comments
Title - Artist
0:00