zqs`s blog

有朋自远方来，虽远必诛

5/11最短路专练总结

发表于 更新于 分类于 Valine：

假装我在写总结，实际上是题解

$A$

原题AT3621。

我们打比赛的时候并不知道这是最短路专练，所以拿到题目第一反应其实是数位 dp。

u1s1我压根没学过更没做过数位dp，只是听过口胡（（（

由于没做过数位 dp 的题，只想到了状态记录 $\mod 10$ 的余数，但这题要记录 $\mod k$ 的余数，然后跑一个最短路。

具体来说，一个正整数一定可以由 $1$ 不断 $\times10$ 或 $+1$ 得到。那么最短路上只需要从每个点 $i$ 向 $i\times 10+j(0\le j\le 9)$ 连边权为 $j$ 的边即可（当然要对 $n$ 取模）。再建立虚拟的编号为 $n$ 的点，向 $0…9 \mod n$ 连边权为 $i$ 的边。然后跑虚拟点 $n$ 到 $0$ 的最短路就可以了。

考试时写了个乱搞骗了 $66$，出题人真良心（

点击显示/隐藏代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <cstdio>
#include <queue>
#include <cstring>

typedef std::pair<int, int> PII;
struct Edge {
	int to, nxt, w;
} e[2000005];
int dis[100005], head[100005], tot, n;
bool done[100005];
std::priority_queue<PII, std::vector<PII>, std::greater<PII> > Q;
inline void AddEdge(const int u, const int v, const int w) {
	e[++ tot].to = v, e[tot].w = w, e[tot].nxt = head[u], head[u] = tot;
}

int Dijkstra() {
	memset(dis, 0x3f, sizeof dis);
	Q.push(std::make_pair(dis[n] = 0, n));
	while (Q.size()) {
		int u = Q.top().second;
		Q.pop();
		if (done[u]) continue;
		if (!u) return dis[u];
		done[u] = true;
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].to;
			if (dis[u] + e[i].w < dis[v])
				Q.push(std::make_pair(dis[v] = dis[u] + e[i].w, v)); 
		}
	}
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; ++ i)
		for (int j(0); j <= 9; ++ j)
			AddEdge(i, (i * 10 + j) % n, j);
	for (int i(1); i <= 9; ++ i) AddEdge(n, i % n, i);
	printf("%d", Dijkstra());
	return 0;
}

$B$

给出 $n$ 个点，$m$ 条边的无向图。一开始从 $1$ 城市出发，有 $S$ 块钱。

每条边形如 $u,v,a,b$，$u,v$ 表示这条边的两个端点，$a$ 表示这条边花费的费用，$b$ 表示经过这条边的耗时。显然如果当前的钱数小于 $a$ 就走不了这条边。

在第 $i$ 个点停留 $k$ 分钟可以获得 $k\times c_i$ 块钱，花费 $k\times d_i$ 的时间。

求 $1$ 到每个点最少需要花费的时间。

$2\le n\le 50,n-1\le m\le 100,0\le S\le 10^9,1\le b,c_i,d_i\le 10^9,1\le a\le 50$，无重边。

题目分析:

明显的分层图单源最短路。$dis_{u,i}$ 表示到达 $u$ 点，还剩 $i$ 块钱的最小耗时。

$i\le 2500$，因为最多经过 $n-1$ 条边，$a_i$ 又只有 $50$，所以大于 $2500$ 全部按这个算就行了。

有一个小问题，如果直接爆枚 $k$ 会超时，那么只需要加一个二进制拆分优化即可。

然而我二进制拆分 lim >= 1 << i 写成了 lim & 1 << i，喜提不如暴力的 $27\texttt{pts}$ /cy/cy/cy

upd：二进制nm，直接转移到 $dis_{u,i+1}$ 就行了，我是伞兵

点击显示/隐藏代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <cstdio>
#include <queue>
#include <cstring>
#define int long long

const int INF = 1e18;
inline int min(const int x, const int y) {return x < y ? x : y;}
struct Node {
	int x, y, z;
	inline bool operator < (const Node a) const {return x > a.x;}
};
struct Edge {
	int to, nxt, a, b;
} e[505];
int head[55], dis[55][2505], C[55], D[55], tot, S, n, m;
bool done[55][2505];
inline void AddEdge(const int u, const int v, const int a, const int b) {
	e[++ tot].to = v, e[tot].nxt = head[u], head[u] = tot;
	e[tot].a = a, e[tot].b = b;
}
std::priority_queue<Node> Q; 

void Dijkstra() {
	memset(dis, 0x3f, sizeof dis);
	Q.push(Node{dis[1][S] = 0, 1, S});
	while (Q.size()) {
		int u(Q.top().y), mon(Q.top().z);
		Q.pop();
		if (done[u][mon]) continue;
		done[u][mon] = true;
		int lim(50 * n / C[u] + 1);
		for (int i(0); i <= 15; ++ i)
			if ((lim >= 1 << i)) {
				int nxt(min(50 * n, mon + (C[u] << i)));
				if (dis[u][mon] + (D[u] << i) < dis[u][nxt])
				Q.push(Node{dis[u][nxt] = dis[u][mon] + (D[u] << i), u, nxt});
			}
		for (int i(head[u]); i; i = e[i].nxt) {
			int v(e[i].to), x(min(n * 50, mon - e[i].a));
			if (0 <= x && dis[u][mon] + e[i].b < dis[v][x])
				Q.push(Node{dis[v][x] = dis[u][mon] + e[i].b, v, x});
		}
	}
}

signed main() {
	scanf("%lld%lld%lld", &n, &m, &S);
	S = min(S, 50 * n);
	for (int i(1); i <= m; ++ i) {
		int u, v, a, b;
		scanf("%lld%lld%lld%lld", &u, &v, &a, &b);
		AddEdge(u, v, a, b), AddEdge(v, u, a, b);
	}
	for (int i(1); i <= n; ++ i) scanf("%lld%lld", C + i, D + i);
	Dijkstra();
	for (int i(2); i <= n; ++ i) {
		int ans(INF);
		for (int j(0); j <= 50 * n; ++ j) ans = min(ans, dis[i][j]);
		printf("%lld\n", ans);
	}
	return 0;
}

$C$

给你一个由 $n$ 个点 $m$ 条边构成的无向图，每条边都有一定的长度。

图中有甲乙两机器人，速度相同，甲从点 $A$ 沿最短路走向 $B$ 点，乙从点 $B$ 沿最短路走向 $A$ 点。 甲乙两机器人存在矛盾，他们路途中相遇就会打架。

问，有多少种走法，他俩在途中不会相遇。 相遇是指同在某个点或者某条边上相遇。 答案可能很大，$\mod 10^9+7$ 后再输出。

$dis1_u$ 表示 $A\rightarrow u$ 的最短路长度，$dis2_u$ 表示 $B\rightarrow u$ 的最短路长度。$cnt1_u$ 表示 $A\rightarrow u$ 的最短路条数，$cnt2_u$ 表示 $B\rightarrow u$ 的最短路条数。

如果在点 $u$ 相遇，那么满足 $dis1_u=dis2_u$，方案数减去 $(cnt1_u\times cnt2_u)^2$。

如果在边 $u\leftrightarrow v$ 相遇（边权为 $w$），那么满足 $dis1_u+dis2_v+w=dis1_B$。方案数减去 $(cnt1_u\times cnt2_v)^2$。

初始时方案数为 $cnt1_B$。

点击显示/隐藏代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <cstdio>
#include <queue>
#include <cstring>
#define int long long

inline int abs(const int k) {return k >= 0 ? k : -k;}
const int mod = 1e9 + 7;
typedef std::pair<int, int> PII;
struct Edge {
	int to, nxt, w;
} e[500005];
int head[100005], dis[100005], cnt[100005], dis1[100005], dis2[100005], cnt1[100005], cnt2[100005], tot, s, t, n, m;
bool done[100005];
std::priority_queue<PII, std::vector<PII>, std::greater<PII> > Q;
inline void AddEdge(const int u, const int v, const int w) {
	e[++ tot].to = v, e[tot].w = w, e[tot].nxt = head[u], head[u] = tot;
}

void Dijkstra(const int s) {
	memset(done, 0, sizeof done);
	memset(dis, 0x3f, sizeof dis);
	Q.push(std::make_pair(dis[s] = 0, s));
	cnt[s] = 1;
	while (Q.size()) {
		int u = Q.top().second;
		Q.pop();
		if (done[u]) continue;
		done[u] = true;
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].to;
			if (dis[u] + e[i].w < dis[v])
				Q.push(std::make_pair(dis[v] = dis[u] + e[i].w, v)), cnt[e[i].to] = cnt[u];
			else if (dis[u] + e[i].w == dis[v])
				cnt[v] = (cnt[u] + cnt[v]) % mod;
		}
	}
}

int work() {
	Dijkstra(s);
	memcpy(dis1, dis, sizeof dis);
	memcpy(cnt1, cnt, sizeof cnt);
	Dijkstra(t);
	memcpy(dis2, dis, sizeof dis);
	memcpy(cnt2, cnt, sizeof cnt);
	int ans = cnt1[t] * cnt2[s];
	for (int i = 1; i <= n; ++ i)
		if (dis1[i] == dis2[i])
			ans = (ans - cnt1[i] * cnt2[i] % mod * cnt1[i] % mod * cnt2[i] % mod) % mod;
//	return (ans + mod) % mod;
	for (int u = 1; u <= n; ++ u)
	for (int i = head[u]; i; i = e[i].nxt)
		if (dis1[u] + dis2[e[i].to] + e[i].w == dis1[t] && abs(dis1[u] - dis2[e[i].to]) < e[i].w)
			ans = (ans - cnt1[u] * cnt2[e[i].to] % mod * cnt1[u] % mod * cnt2[e[i].to] % mod) % mod;
	return (ans + mod) % mod;
}

signed main() {
	scanf("%lld%lld%lld%lld", &n, &m, &s, &t);
	for (int i = 1; i <= m; ++ i) {
		int u, v, w;
		scanf("%lld%lld%lld", &u, &v, &w);
		AddEdge(u, v, w), AddEdge(v, u, w);
	}
	printf("%lld\n", work());
	return 0;
}
-------------本文结束感谢您的阅读-------------