new

路径难题

Solution

因为就10组询问，所以直接跑10遍最短路即可

将每组公交车站点建个虚点，连进边权为0的边，连出价格 × r 的边，如果跑最短路的过程中接下来走公交车，那么先上取整更新距离，

再加上这条边权，因为每次乘出租车都要上取整，最后用最终的最小距离上取整算价格就行

Code

Code

#include <bits/stdc++.h>
#define rint register int
using namespace std;

char buf[1 << 20], *p1, *p2;
#define gc() (p1 == p2 ? (p2 = buf + fread(p1 = buf, 1, 1 << 20, stdin), p1 == p2 ? EOF : *p1++) : *p1++)
#define read() ({
	rint x = 0; register bool f = 0; register char ch = gc();
	for(;!isdigit(ch);ch = gc()) f |= ch == '-';
	for(; isdigit(ch);ch = gc()) x = (x << 3) + (x << 1) + (ch & 15);
	f ? -x : x ;
})

const int maxn = 2e5 + 1e4 + 10;
const int maxm = 4e5 + 8e5 + 10;
int n, m, cnt, k, q;
int head[maxn];
long long r, f[maxn];
bool vis[maxn];
struct Edge{
	int to, next;
	long long val;
	bool op;
}e[maxm];

void add(rint x, rint y, long long z, bool tp = 0){
	e[++cnt] = (Edge){y, head[x], z, tp};
	head[x] = cnt;
}

long long dij(rint s, rint t){
	priority_queue < pair<long long, int> > q;
	memset(vis, 0, sizeof vis);
	memset(f, 0x3f, sizeof f);
	f[s] = 0, q.push(make_pair(0, s));
	while(!q.empty()){
		const int x = q.top().second;
		q.pop();
		if(x == t) return (f[t] - 1) / r + 1;
		if(vis[x]) continue;
		vis[x] = 1;
		for(rint i = head[x], y;i;i = e[i].next){
			y = e[i].to;
			if(f[y] > f[x] + e[i].val){
				f[y] = (e[i].op == 1 && f[x] > 0) ? (((f[x] - 1) / r + 1) * r + e[i].val) : (f[x] + e[i].val);
				q.push(make_pair(-f[y], y));
			}
		}
	}
	return (f[t] - 1) / r + 1;
}

int main(){
	freopen("route.in","r",stdin);
	freopen("route.out","w",stdout);
	n = read(), m = read(), k = read(), r = read(), q = read();
	for(rint i = 1, x, y, z;i <= m; ++i) x = read(), y = read(), z = read(), add(x, y, z), add(y, x, z);
	for(rint i = 1, t, c, x;i <= k; ++i){
		t = read(), c = read();
		for(rint j = 1;j <= t; ++j) x = read(), add(x, i + n, 0, 1), add(i + n, x, 1ll * c * r, 1);
	}
	for(rint i = 1, x, y;i <= q; ++i){
		x = read(), y = read();
		printf("%lld
", dij(x, y));
	}
	return 0;
}