题解：CF1915G Bicycles

思路：分层图最短路

明显，在有多辆车的情况下，使用速度系数最小的车最优。

但是，如果直接跑普通的最短路，样例会过不了。

为什么？

首先观察样例所建的图：

当从

1

到

2

时所花的时间是

10

。如果直接跑最短路的话，路径是

1 \to 2 \to 4 \to 5

。总时间是

2 \times 5 + 2 \times 5 + 2\times 1 = 22

。

但是，实际上路径为

1 \to 2 \to 3 \to 2 \to 4 \to 5

是会更优的，总时间是

2 \times 5 + 1 \times 2 + 1 \times 1 + 5 \times 1 + 1\times 1 = 19

。观察两个路径的区别，不难发现，在第二种中虽然重复走了两遍

2 \to 3

但这换取了速度系数更小，使得总时间更少。

所以我们对于每一个速度系数建一个层，跑一遍分层图最短路即可。注意能往下一层转移的，就不必再在同层转移了。

对比：

对于答案，即为

\min^{1000}_{i = 1} d_{n,i}

。其中

d_{i,j}

表示从

1

到

i

，且最小速度系数最小值为

j

时的最短时间。

code：

CPP

#include <bits/stdc++.h>
using namespace std;

#define inf 0x7fffffffffffffff
int n, m;

struct V{
	int s;
	vector<array<int, 2> > e;
	long long d[1009];
	bitset<1009> c;
}v[1009];

priority_queue<array<long long, 3>, vector<array<long long, 3> >, greater<array<long long, 3> > > p;

inline void dij() {
	p.push({0, 1, v[1].s});
	v[1].d[v[1].s] = 0;
	while(p.size()) {
		int u = p.top()[1];
		int k = p.top()[2];
		p.pop();
		if(v[u].c[k]) continue;
		v[u].c = 1;

		for(auto to: v[u].e) {
			if(v[to[0]].d[min(k, v[to[0]].s)] > v[u].d[k] + to[1] * k) {
				v[to[0]].d[min(k, v[to[0]].s)] = v[u].d[k] + to[1] * k;
				p.push({v[to[0]].d[min(k, v[to[0]].s)], to[0], min(k, v[to[0]].s)});
			}
		}
	}
}

inline void sovel() {
	cin >> n >> m;
	fill(v + 1, v + n + 1, v[0]);
	for(int i = 1, _u, _v, _w; i <= m; i++) {
		cin >> _u >> _v >> _w;
		v[_u].e.push_back({_v, _w});
		v[_v].e.push_back({_u, _w});
	}
	for(int i = 1; i <= n; i++) {
		fill(v[i].d + 1, v[i].d + 1001, inf);
		cin >> v[i].s;
	}
	dij();
	long long ans = inf;
	for(int i = 1; i <= 1000; i++) {
		ans = min(ans, v[n].d[i]);
	}
	cout << ans << "\n";
}

int main() {

	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int _T = 1;
	cin >> _T;
	while(_T--) {
		sovel();
	}

	return 0;

}

题解：CF1915G Bicycles

文章操作

思路：分层图最短路

相关推荐

评论

题解：CF1915G Bicycles