首页 > 滴滴笔试9.13 修桥一直只有36%,有没有大佬看看代码问题
头像
autocoder
编辑于 2020-09-13 21:40
+ 关注

滴滴笔试9.13 修桥一直只有36%,有没有大佬看看代码问题

滴滴笔试9.13 修桥联通为什么一直只有36%,有没有大佬看看代码问题

具体题目是:

D星群岛由n个小岛组成。为了加强小岛居民之间的交流,头目决定启动一个造桥工程,将全部n个岛连接到一起。

由于受到金融危机的影响,头目要求造桥的总成本要最少,并且还规定每一座桥的成本都不能超过k万D星币。

需要注意的是,由于受到地理环境和气候影响,有些小岛之间没有办法直接造桥。

现在给你m条小岛之间的造桥成本数据以及k的值,请问这个宏伟的造桥工程是否能够顺利完成?

注意:可能边不够,也可能费用超支。

输入描述
多组输入,第1行输入一个正整数T表示输入数据的组数。
对于每一组输入数据:输入m+1行。
第1行包含三个正整数,分别表示n、m和k,n≤100,m≤1000,k≤10000,三个数字之间用空格隔开。
接下来m行表示m条小岛之间的造桥成本数据,每一行包含三个正整数,分别表示两个小岛的编号(从1开始)和这两个小岛之间的造桥成本(单位:万)。

输出描述
针对每一组输入数据,如果能够完成造桥工程输出“Yes”,否则输出“No”。

样例输入
2
3 3 400
1 2 200
1 3 300
2 3 500
3 3 400
1 2 500
1 3 600
2 3 700

样例输出
Yes
No


#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
void dfs(int i, unordered_map<int, vector<int>> &qz, vector<bool> &visited) {
	visited.at(i - 1) = 1;
	for (int var = 0; var < qz[i].size(); ++var) {
		if (!visited.at(qz[i].at(var) - 1)) {
			dfs(qz[i].at(var), qz, visited);
		}
	}
}
int main() {
	int zu;
	cin >> zu;
	for (int var = 0; var < zu; ++var) {
		int n, m, k;
		while (cin >> n >> m >> k) {
			vector<bool> visited(n, 0);
			unordered_map<int, vector<int>> qz;
			for (int var = 0; var < m; ++var) {
				int qi;
				int z;
				int q;
				cin >> qi >> z >> q;
				if (q <= k) {
					qz[qi].push_back(z);
				}
			}
			dfs(1, qz, visited);
			bool ok = 1;
			for (int var = 0; var < visited.size(); ++var) {
				if (!visited.at(var)) {
					ok = 0;
					break;
				}
			}
			if (ok) {
				cout << "Yes" << endl;
			} else {
				cout << "No" << endl;
			}
		}
	}
	return 0;
}


全部评论

(3) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

热门推荐