中转站

题目描述

\(Kiana\) 最近兼职起了快递工作，每天早上她都会从家里出发，先到中转站去接今天要送的快递清单，再将快递送到相应的地址去。

可乐城一共有 \(n\) 个地点，\(m\) 条双向道路将这些地点连通，使得任意两个地点之间都能够通过道路相互到达。\(Kiana\) 的家所在地点的编号为 \(s\)，而由于可乐城快递业合理的工作区域划分机制，\(Kiana\) 需要将快递送达的地址集中在一个地点上，其编号为 \(t\)。同样仰仗于快递业的发达，城中共有 \(k\) 个地点设置了快递中转站，其中第ii个地点的编号为 \(r_i\)。

因为交通状况可能不同，所以 \(Kiana\) 通过每条道路所需的时间是不同的，其中通过第ii条道路所需的时间为 \(a_i\)。\(Kiana\) 可以自己决定让快递公司将自己要送的快递运输到哪一个中转站去，使得她从家到中转站再从中转站到目的地所花的总时间尽可能少。

现在 \(Kiana\) 想知道，自己送快递所需的总时间最少是多少。由于 \(Kiana\) 自己不会算，所以希望你能够帮助她。

输入输出格式

输入格式

第一行包含五个正整数 \(n,m,s,t,k\)，分别表示可乐城中的地点数、双向道路数、\(Kiana\) 的家所在的地点编号、送快递的目的地编号和可乐城中的中转站数量。

第二行包含 \(k\) 个正整数，其中第 \(i\) 个数 \(r_i\) 表示第ii个中转站的编号为 \(r_i\)。

接下来 \(m\) 行，其中第 \(i\) 行包含三个正整数 \(u_i,v_i,a_i\)，表示在地点 \(u_i\) 和 \(v_i\) 之间有一条双向道路，\(Kiana\) 通过这条道路所需的时间为 \(a_i\)。

输入保证中转站的编号两两不同，任意两个地点之间至多只有一条双向道路，且没有一个地点和自己之间有道路。

输出格式

输出共一行，包含一个非负整数，表示 \(Kiana\) 送快递所需的最少总时间。

输入输出样例

输入样例#1：

5 6 1 5 3
2 3 4
1 2 5
1 3 2
1 4 6
2 5 4
3 5 3
4 5 1

输出样例#1：

5

输入样例#2：（^_^）

151 164 146 31 61
73 95 98 25 130 69 138 30 91 39 75 120 148 112 107 63 102 105 24 90 27 40 57 8 9 67 118 11 145 150 106 94 59 42 101 100 49 99 119 68 58 45 125 60 80 109 71 28 124 23 88 127 116 133 84 97 132 87 51 64 44
7 33 60
56 90 3
41 90 3
93 63 5
53 107 8
124 127 27
23 86 7
33 36 192
6 101 85
89 134 5
82 64 10
20 59 4
37 122 97
7 37 8
97 90 9
112 92 10
17 143 8
2 128 9
37 80 7
115 63 6
44 148 3
22 43 8
8 110 10
112 108 20
50 112 10
143 71 2
140 130 3
25 41 9
16 86 7
86 14 6
95 120 9
54 151 10
15 133 8
42 27 1
108 139 10
124 150 4
123 59 9
67 24 9
131 142 4
4 54 1
49 94 5
40 106 10
62 151 7
119 64 164
147 9 7
141 27 88
96 66 5
117 51 7
64 34 3
113 40 2
78 42 3
126 121 4
13 30 1
36 120 1
26 102 2
74 5 8
21 37 8
144 44 2
60 132 7
69 55 20
109 99 5
52 123 4
114 104 9
65 21 2
75 5 3
88 39 9
32 146 10
92 96 8
9 32 3
94 12 6
101 61 10
34 90 4
19 88 1
103 4 2
18 45 6
145 109 3
105 137 9
59 96 8
135 91 7
132 66 6
127 2 10
79 116 10
139 105 9
28 5 8
33 57 2
104 95 6
55 53 6
11 9 4
51 106 5
24 122 8
116 95 3
100 75 3
35 26 2
71 145 8
43 107 7
3 148 9
121 12 9
91 127 1
80 48 9
82 105 172
48 40 7
128 146 8
39 121 6
125 67 10
6 118 6
99 136 9
66 72 7
118 15 5
63 114 5
84 62 1
119 62 7
136 37 2
87 7 6
98 103 1
133 103 2
69 40 5
130 66 1
129 52 2
138 6 7
95 50 7
151 88 6
137 133 6
110 138 8
141 107 7
72 6 2
46 85 4
134 53 2
77 26 1
27 1 8
90 35 7
73 28 5
148 124 3
57 75 6
120 81 5
38 107 6
107 100 6
45 49 2
149 80 2
86 90 108
12 1 8
111 79 9
58 104 4
29 51 8
81 60 2
106 134 5
86 139 93
47 86 9
68 127 6
10 84 5
150 97 7
102 2 5
30 151 1
76 71 2
142 52 1
70 138 1
5 82 5
1 16 4
61 109 1
31 111 2
83 80 4
150 16 99
122 10 5
14 61 2
85 3 2

输出样例#2：

285

样例解释

在输入输出样例1中，可乐城共有 \(5\) 个地点和 \(6\) 条有向边，\(Kiana\) 的家在地点 \(1\)，送快递的目的地在地点 \(5\)，共有 \(3\) 个地点有中转站，编号分别为 \(2,3,4\)。

如果选择 \(2\) 号地点作为中转站，则 \(Kiana\) 的最优送快递路线为 \(1\to2\to5\)，总时间为 \(9\)。

如果选择 \(3\) 号地点作为中转站，则 \(Kiana\) 的最优送快递路线为 \(1\to3\to5\)，总时间为 \(5\)。

如果选择 \(4\) 号地点作为中转站，则 \(Kiana\) 的最优送快递路线为 \(1\to4\to5\)，总时间为 \(7\)。

综上所述，\(Kiana\) 会选择 \(3\) 号地点作为中转站，此时所需的总时间最少为 \(5\)。

数据范围

对于 \(30\%\) 的数据，保证 \(1≤n≤200,1≤m≤500\)。

对于 \(60\%\) 的数据，保证 \(1≤n≤2000,1≤m≤5000\)。

对于 \(100\%\) 的数据，保证 \(1≤k≤n≤200000,1≤m≤500000,1≤s,t,ri,ui,vi≤n,1≤ai≤1000\)。

分析

• 考虑到存在中转站，且中转站是必须经过一个的，因此可以尝试从起点 \(s\) 和终点 \(t\) 向中转站出发，去两段路程之和。
• 若是从中转站向 \(s\) 和 \(t\) 出发，根据题目数据可知，\(k\) 最坏情况可以到达 \(200000\)，那么从中转站出发明显不理智，故应从 \(s\) 和 \(t\) 向中转站出发。

代码

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>

const int N = 2e5 + 10;
const int M = 5e5 + 25;

int n, m, s, t, k;
int ans1[N], ans2[N], r[N];
bool vis[N];

struct Edge {
	int to, value, next;
} E[M << 1];
int H[N], cnt;

inline void addEdge(int u, int v, int w) {
	E[++cnt] = (Edge) {
		v, w, H[u]
	};
	H[u] = cnt;
}

struct QueueNode {
	int dis, now;
	bool operator < (const QueueNode& rhs) const {
		return dis > rhs.dis;
	}
};

std::priority_queue<QueueNode> q;
void dfs1() {
	while (q.size()) {
		q.pop();
	}
	
	memset(ans1, 0x3f3f3f3f, sizeof ans1);
	memset(vis, 0, sizeof vis);
	
	q.push((QueueNode){
		0, s
	});
	ans1[s] = 0;
	
	while (q.size()) {
		int u = q.top().now; q.pop();
		
		if (vis[u]) {
			continue;
		}
		vis[u] = 1;
		
		for (int i = H[u]; i; i = E[i].next) {
			int v = E[i].to;
			int w = E[i].value;
			
			if (ans1[v] > ans1[u] + w) {
				ans1[v] = ans1[u] + w;
				q.push((QueueNode){
					ans1[v], v
				});
			}
		}
	}
}

void dfs2() {
	while (q.size()) {
		q.pop();
	}
	
	memset(ans2, 0x3f3f3f3f, sizeof ans2);
	memset(vis, 0, sizeof vis);
	
	q.push((QueueNode){
		0, t
	});
	ans2[t] = 0;
	
	while (q.size()) {
		int u = q.top().now; q.pop();
		
		if (vis[u]) {
			continue;
		}
		vis[u] = 1;
		
		for (int i = H[u]; i; i = E[i].next) {
			int v = E[i].to;
			int w = E[i].value;
			
			if (ans2[v] > ans2[u] + w) {
				ans2[v] = ans2[u] + w;
				q.push((QueueNode){
					ans2[v], v
				});
			}
		}
	}
}

int main(void) {
	scanf("%d %d %d %d %d", &n, &m, &s, &t, &k);
	for (int i = 0; i < k; ++i) {
		scanf("%d", r + i);
	}
	for (int i = 0, u, v, a; i < m; ++i) {
		scanf("%d %d %d", &u, &v, &a);
		
		addEdge(u, v, a);
		addEdge(v, u, a);
	}
	
	dfs1();
	dfs2();
	
	int ans = 0x3f3f3f3f;
	for (int i = 0; i < k; ++i) {
		ans = std::min(ans, ans1[r[i]] + ans2[r[i]]);
	}
	
	printf("%d", ans);
	
	return 0;
}

粒子自撞机

题目描述

\(Kiana\) 上物理课时学习到了粒子对撞机的前沿八卦，为了学以致用，她自己构思出了一个类似的模型，称为粒子自撞机。

在粒子自撞机中，\(0\) 时刻一个粒子会从数轴上的 \(0\) 位置出发，每经过 \(1\) 个时刻粒子会向右运动 \(a\) 的距离，也即在 \(1\) 时刻粒子会到达 \(a\) 位置、\(2\) 时刻会到达 \(2a\) 位置，依此类推。数轴上 \(0\) 位置处和 \(b\) 位置处各有一块反射板，如果粒子在运动过程中碰到了反射板，则会立刻改变运动方向，但不会影响运动的总距离，换言之粒子会不断地在 \(0\) 位置和 \(b\) 位置之间来回移动，形成自撞。

现在 \(Kiana\) 想知道，粒子第一次在整数时刻运动到 \(c\) 位置时，该时刻值是多少。由于 \(Kiana\) 自己不会算，所以希望你能够帮助她。

输入输出格式

输入格式

第一行包含三个正整数 \(a,b\) 和 \(c\)，分别表示粒子每时刻运动的距离、反射板的位置和询问的位置。

输入保证粒子会在某个整数时刻运动到位置 \(c\)，即问题一定是有解的。

输出格式

输出共一行，包含一个正整数，表示粒子第一次在整数时刻运动到 \(c\) 位置时的时刻值。

输入输出样例

输入样例#1：

3 5 1

输出样例#1：

3

输入样例#2：

3 6 6

输出样例#2：

2

输入样例#3：

3327 9389 8570

输出样例#3：

8576

样例解释

在输入输出样例1中，粒子每时刻运动的距离为 \(3\)，在 \(0\) 位置和 \(5\) 位置各有一块反射板，\(Kiana\) 询问的是粒子最早运动到 \(1\) 位置的整数时刻值。

粒子的运动轨迹是：\(1\) 时刻运动到 \(3\) 位置，\(2\) 时刻本应该运动到 \(6\) 位置，但受到反射板影响，最终实际是运动到了 \(4\) 位置，\(3\) 时刻运动到 \(1\) 位置，所以所求答案为\(3\)，如果粒子继续运动，\(4\) 时刻会运动到 \(2\) 位置。注意到粒子在第 \(1\) 时刻的运动中到达过一次 \(1\) 位置，但不是整数时刻到达的。

在输入输出样例2中，粒子每时刻运动的距离为 \(3\)，在 \(0\) 位置和 \(6\) 位置各有一块反射板，\(Kiana\) 询问的是粒子最早运动到 \(6\) 位置的整数时刻值。

粒子的运动轨迹是：\(1\) 时刻运动到 \(3\) 位置，\(2\) 时刻运动到 \(6\) 位置，所以所求答案为 \(2\)，如果粒子继续运动，\(3\) 时刻本应该运动到 \(9\) 位置，但受到反射板影响，最终实际是运动到了 \(3\) 位置。

数据范围

对于 \(20\%\) 的数据，保证 \(1≤a,c≤b≤100\)。

对于 \(40\%\) 的数据，保证 \(1≤a,c≤b≤10000\)。

对于 \(60\%\) 的数据，保证 \(1≤a,c≤b≤10^6\)。

对于 \(100\%\) 的数据，保证 \(1≤a,c≤b≤10^9\)。

分析

• 注意要开 long long，long long yyds，这是一个将我从 \(100\) 分击落到 \(40\) 分的好家伙！！！！！！！！！！\((QAQ)\)

• 下面开始正文

• 分析题目，其实就是粒子在两个板之间来回弹（废话）

• 那么当粒子从 \(0\) 位置走到 \(b\) 位置的时候，粒子满足的方程应该为 \(a x\equiv c\ (mod \ 2b)\)

• 当粒子从 \(b\) 位置走到 \(0\) 位置的时候，粒子满足的方程应该为 \(a x \equiv 2 b - c\ (mod\ 2b)\)

• (想想为什么？)

• 其实粒子从 \(0\) 到 \(b\) 和从 \(b\) 到 \(0\) 走的路程是一个相反的过程，我们可以将这两个过程当一个周期展开放在一起，那么就是从 \(0\) 到 \(2b\) 的一个过程，其中 \(0\) 到 \(b\) 的过程中的 \(c\) 点，此时还在 \(c\) 点；\(b\) 到 \(0\) 的过程中的 \(c\) 点，相当于从 \(2b\) 位置回走 \(c\) 单位长度，也就是 \(2b-c\) 的位置，可以自己画图试一试，至于为什么我没有图……这就是一个值得思考的问题了（懒）

  ---

• 然后就是对上面两个式子进行剖析了。

• 对于 \(ax\equiv c\ (mod\ 2b)\) 而言，一定会有一个整数 \(y\) 可以使 \(ax=c+2by\) 成立。

• 移项一下，\(ax-2by = c\)

• 我们用 \(m\) 来表示一下 \(-2b\)，也就是令 \(m=-2b\)

• 那么式子就可以转化成 \(ax+my=c\)，这是什么，不定方程啊，那不就好起来了吗？

• 想一想，我们不是做过 \(ax+by\equiv 1\ (mod\ n)\) 的不定方程吗？

• 那么这个不一样吗？

• 我们可以将式子转化成那个不定方程，上述不定方程其实就是 \(a\) 与 \(b\) 互质，也就是 \(ax+by=\gcd(a,b)\)

• 我们这个式子不也可以转化吗？

• 两边同时乘上 \(\frac{\gcd(a,m)}{c}\) 不就行了？

• 为了方便，我们可以将新的 \(x\) 和 \(y\) 记作 \(x_0\) 和 \(y_0\)，那么就有新式子 \(ax_0+my_0=\gcd(a,m)\)

• 可以用扩展欧几里得算法将这个特殊的式子中个 \(x_0\) 和 \(y_0\) 解出来，我们称其为 特解

• 接着，我们可以将其带入原先的式子，得到 \(ax_0+my_0=c\)

• 我们用原式和这个新的式子相减，可以得到 \(a(x-x_0)+m(y-y_0)=0\)

• 将 \(m(y-y_0)\) 移至右侧，并两边同时除以 \(\gcd(a,m)\)，可以得到 \(\frac{a}{\gcd(a,m)}(x-x_0)=-\frac{m}{\gcd(a,m)}(y-y_0)\)

• 有个结论是 \(\gcd(\frac{a}{\gcd(a,m)},\frac{m}{\gcd(a,m)})=1\)

• 而这又是一个整数方程

• \(\frac{a}{\gcd(a,m)}\) 与 \(\frac{m}{\gcd(a,m)}\) 互质

• 要相等的话，\((x-x_0)\) 就应当是 \(\frac {m}{\gcd(a,m)}\) 的倍数

• 那么，就会存在一个整数 \(t\) 可以使 \(x-x_0=t\times\frac{m}{\gcd(a,m)}\) 成立

• 故 \(x=x_0+t\times\frac{m}{\gcd(a,m)}\)

• 此题需要最小的解，那么也就是 \(t=0\) 时，也就是解应该与 \(x_0\) 有关

• 为什么不是 \(x_0\) 呢？

• 因为 \(x_0\) 是在乘了 \(\frac{\gcd(a,m)}{c}\) 后得到的答案！

• 我们需要的答案应该要再乘一个 \(\frac{c}{\gcd(a,m)}\)！

• 那么答案就是 \(x_0\times\frac{c}{\gcd(a,m)}\)

• 至于 \(ax\equiv 2b-c\ (mod\ 2b)\) 这个式子，emm，用换元法！（我不想打了），将上面过程中的 \(c\) 换成 \(2b-c\) 就是过程了！

代码

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll; // long long 是神，是至高无上的神明，ta能霸占足足60分

ll exgcd(ll a, ll b, ll &x, ll &y) {
	if (!b) {
		x = 1;
		y = 0;
		return a;
	}
	ll g = exgcd(b, a % b, x, y);
	ll t = x;
	x = y;
	y = t - a / b * y;
	return g;
}

int main(void) {
	ll a, b, c;
	cin >> a >> b >> c;
	
	b = -2 * b;
	ll x1, y1, x2, y2;
	ll g1 = exgcd(a, b, x1, y1);
	ll g2 = exgcd(a, b, x2, y2);
	
	x1 = (x1 * (c / g1) % b + b) % b;
	x2 = (x2 * ((b - c) / g2) % b + b) % b;
	
	cout << min(x1, x2);
	
	return 0;
}

（\(ps:\) 有生之年系列，我什么时候想起来了就更！！）

迷途大盗（To be continued)

路灯(To be continued)