【CCPC】The 2021 CCPC Guilin Onsite (XXII Open Cup, Grand Prix of EDG) K

Tax

#图论 #最短路 #搜索 #暴力

题目描述

JB received his driver’s license recently. To celebrate this fact, JB decides to drive to other cities in Byteland. There are $n$ cities and $m$ bidirectional roads in Byteland, labeled by $1,2,\dots ,n$. JB is at the $1$-st city, and he can only drive on these $m$ roads. It is always possible for JB to reach every city in Byteland.

The length of each road is the same, but they are controlled by different engineering companies. For the $i$-th edge, it is controlled by the $c_i$-th company. If it is the $k$-th time JB drives on an edge controlled by the $t$-th company, JB needs to pay $k\times w_t$ dollars for tax.

JB is selecting his destination city. Assume the destination is the $k$-th city, he will drive from city $1$ to city $k$ along the shortest path, and minimize the total tax when there are multiple shortest paths. Please write a program to help JB calculate the minimum number of dollars he needs to pay for each possible destination.

输入格式

The input contains only a single case.

The first line of the input contains two integers $n$ and $m$ ($2\le n\le 50$, $n-1\le m\le \frac{n(n-1)}{2}$), denoting the number of cities and the number of bidirectional roads.

The second line contains $m$ integers $w_1,w_2,\dots ,w_m$ ($1\le w_i\le 10000$), denoting the base tax of each company.

In the next $m$ lines, the $i$-th line $(1\le i\le m)$ contains three integers $u_i,v_i$ and $c_i$ ($1\le u_i,v_i\le n$, $u_i\ne v_i$, $1\le c_i\le m$), denoting denoting an bidirectional road between the $u_i$-th city and the $v_i$-th city, controlled by the $c_i$-th company.

It is guaranteed that there are at most one road between a pair of city, and it is always possible for JB to drive to every other city.

输出格式

Print $n-1$ lines, the $k$-th ($1\le k\le n-1$) of which containing an integer, denoting the minimum number of dollars JB needs to pay when the destination is the $(k+1)$-th city.

样例 #1

样例输入 #1

5 6
1 8 2 1 3 9
1 2 1
2 3 2
1 4 1
3 4 6
3 5 4
4 5 1

样例输出 #1

1
9
1
3

解法

首先图只有$n\le 50$，并且每条边的权值都为$1$，那么我们可以使用$bfs$或者$floyed$ 求出$1$号点到其他任何点的最短路径。

然后就可以枚举所有的合法的最短路径了， 由于图很小，所以直接大力$dfs$ 搜索所有可能的情况，维护最小值即可。

代码（floyed）

void solve() {
	int n, m;
	std::cin >> n >> m;

	std::vector<int>w(m + 1);
	for (int i = 1; i <= m; ++i) {
		std::cin >> w[i];
	}

	std::vector<std::vector<int>>dis(n + 1, std::vector<int>(n + 1, inf));

	std::vector<std::vector<pii>>e(n + 1);
	for (int i = 1; i <= m; ++i) {
		int u, v, c;
		std::cin >> u >> v >> c;

		e[u].push_back({ v,c });
		e[v].push_back({ u,c });

		dis[u][v] = dis[v][u] = 1;
	}

	auto floyed = [&]() {
		for (int i = 1; i <= n; ++i) {
			dis[i][i] = 0;
		}
		for (int k = 1; k <= n; ++k) {
			for (int i = 1; i <= n; ++i) {
				for (int j = 1; j <= n; ++j) {
					dis[i][j] = std::min(dis[i][j], dis[i][k] + dis[k][j]);
				}
			}
		}
		};

	floyed();

	std::vector<int>cnt(m + 1);
	std::vector<int>d(n + 1, inf);
	auto dfs = [&](auto&& self, int u, int sum)->void {

		d[u] = std::min(d[u], sum);
		for (auto& [v, c] : e[u]) {
			if (dis[1][u] + 1 == dis[1][v]) {
				cnt[c]++;
				self(self, v, sum + cnt[c] * w[c]);
				cnt[c]--;
			}
		}
		};

	dfs(dfs, 1, 0);

	for (int i = 2; i <= n; ++i) {
		std::cout << d[i] << "\n";
	}

}

signed main() {
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);
	std::cout.tie(0);

	int t = 1;
	//std::cin >> t;

	while (t--) {
		solve();
	}

	return 0;
}

代码（bfs）

 
void solve() {
	int n,m;
	std::cin >> n>>m;
 
	std::vector<int>w(m + 1);
	for (int i = 1; i <= m; ++i) {
		std::cin >> w[i];
	}
 
	std::vector<std::vector<pii>>e(n + 1);
	for (int i = 1; i <= m; ++i) {
		int u, v, c;
		std::cin >> u >> v >> c;
 
		e[u].push_back({ v,c });
		e[v].push_back({ u,c });
	}
 
 
	std::vector<bool> vis(n + 1);
	std::vector<int>dis(n + 1);
	auto bfs = [&]() {
		std::queue<pii>q;
	
		q.push({ 1,0 }); vis[1] = 1;
			
		while (q.size()) {
			auto [u, d] = q.front(); q.pop();
 
			for (auto& [v, c] : e[u]) {
				if (vis[v]) continue;
				
				dis[v] = dis[u] + 1;
				q.push({ v,dis[v] });
				vis[v] = 1;
			}
		}
		};
 
	bfs();
 
	std::vector<int>cnt(m + 1);
	std::vector<int>d(n + 1, inf);
	auto dfs = [&](auto &&self ,int u,int sum)->void {
 
		d[u] = std::min(d[u], sum);
		for (auto& [v, c] : e[u]) {
			if (dis[u] + 1 == dis[v]) {
				cnt[c]++;
				self(self, v, sum + cnt[c] * w[c]);
				cnt[c]--;
			}
		}
		};
 
	dfs(dfs, 1, 0);
	
	for (int i = 2; i <= n; ++i) {
		std::cout << d[i] << "\n";
	}
 
}
 
signed main() {
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);
	std::cout.tie(0);
 
	int t = 1;
	//std::cin >> t;
 
	while (t--) {
		solve();
	}
 
	return 0;
}