【蓝桥杯】第十三届蓝桥杯C++B组国赛（难出新高度）

原题：[https://data.fivk.cn/down.php/9a13cd7c281f6be0d7376606aeea86ee.pdf](https://data.fivk.cn/down.php/9a13cd7c281f6be0d7376606aeea86ee.pdf)

其他看懂点的题目就暴力，下面个题目也不知道能骗点分不，先放这里了，不想多说什么了qvq
</div>

## 试题 E: 出差

```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 1e3 + 10, M = 1e4 + 10;
int n, m;
int a, b, c;

int f[N][N];
int dis[M];
int st[M];
int time[N];

int main() {
	memset(f, 0x3f, sizeof f);
	memset(dis, 0x3f, sizeof dis);
	scanf("%d %d", &n, &m);

for (int i = 1; i <= n; i ++) {
		scanf("%d", &time[i]);
	}

for (int i = 1; i <= m; i ++) {
		scanf("%d %d %d", &a, &b, &c);
		f[a][b] = min(f[a][b], c + time[b]);
		f[b][a] = min(f[b][a], c + time[a]);
	}

dis[1] = 0;

for (int i = 1; i <= n; i ++) {
		int k = -1;
		for (int j = 1; j <= n; j ++) {
			if (!st[j] && (k == -1 || dis[k] > dis[j])) {
				k = j;
			}
		} 
		if (k == -1) break;
		st[k] = true;

// 更新其余边

for (int j = 1; j <= n; j ++) {
			if (!st[j]) {
				dis[j] = min(dis[j], dis[k] + f[k][j]);
			}
		} 
	}

printf("%d  ", dis[n] - time[n]);

return 0;
}
```

## 试题 H: 机房

```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 1e5 + 10;

int h[N], e[N], ne[N], idx;
bool st[N];
int cnt[N];
int n, m, a, b;

void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int main() {
	memset(h, -1, sizeof h);
	scanf("%d %d", &n, &m);
	for (int i = 1; i < n; i ++) {
		scanf("%d %d", &a, &b);
		cnt[a] ++;
		cnt[b] ++;
		add(a, b);
		add(b, a);
	}
	int hhh = -1;
	for (int i = 1; i <= n; i ++) {
		if (cnt[i] == 1) {
			hhh = i;
			break;
		}
	}

int q[N], hh = 0, tt = 1;
	q[0] = hhh;

while (hh < tt) {
		int t = q[hh ++];
		st[t] = true;
		for (int i = h[t]; i != -1; i = ne[i]) {
			int j = e[i];
			if (!st[j]) q[tt ++] = j;
		}
	}

for (int i = 1; i <= m; i ++) {
		scanf("%d %d", &a, &b);
		if (a == b) {
			printf("1\n");
			continue;
		}
		bool flag = false;
		int index = 0;
		int ans = 0;
		for (int i = 0; i < tt; i ++) {
			if (q[i] == a || q[i] == b) {
				flag = true;
			}
			if (flag) {
				ans += cnt[q[i]];
				if (index && (q[i] == b || q[i] == a)) {
					flag = false;
					break;
				}
				index = 1;
			} 
		}

printf("%d\n", ans);
	}

return 0;
}
```

最后修改：2022 年 06 月 19 日