icontofig | 发布于 2019-07-02 22:54:54 | 阅读量 89 | 最短路
发布于 2019-07-02 22:54:54 | 最短路

题解

保证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;
}



内容更新于: 2019-07-02 22:54:57
链接地址: http://blog.leanote.com/post/icontofig/187c8617f20c

上一篇: 洛谷P1073 最优贸易 分层图SPFA

下一篇: BZOJ 3527 [ZJOI2014]力 FFT模板题

89 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航