请生成这道题的c++代码:问题描述 A市有n个交通枢纽,其中1号和n号非常重要,为了加强运输能力,A市决定在1号到n号枢纽间修建一条地铁。 地铁有很多段隧道组成,每段隧道连接两个交通枢纽。经过勘探,有m段隧道作为候选,两个交通枢纽之间最多只有一条候选的隧道,没有隧道两端连接着同一个交通枢纽。 现在有n家隧道施工的普通公司和一家王牌公司,每段候选的隧道只能由一个公司施工,普通公司施工需要的天数一致,王牌公司需要的天数是普通公司的三分之一(四舍五入到整数)。而每家公司最多只能修建一条候选隧道。所有公司同时开始施工。 作为项目负责人,你获得了候选隧道的信息,现在你可以按自己的想法选择一部分隧道进行施工并规定施工的公司,请问修建整条地铁最少需要多少天。 输入格式 输入的第一行包含两个整数n, m,用一个空格分隔,分别表示交通枢纽的数量和候选隧道的数量。 第2行到第m+1行,每行包含三个整数a, b, c,表示枢纽a和枢纽b之间可以修建一条隧道,普通公司需要的时间为c天。 输出格式 输出一个整数,修建整条地铁线路最少需要的天数。
时间: 2024-04-05 19:33:33 浏览: 49
以下是生成的C++代码:
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Tunnel {
int from;
int to;
int days;
};
bool compare(Tunnel t1, Tunnel t2) {
return t1.days < t2.days;
}
int main() {
int n, m;
cin >> n >> m;
vector<Tunnel> tunnels(m);
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
tunnels[i].from = a;
tunnels[i].to = b;
tunnels[i].days = c;
}
sort(tunnels.begin(), tunnels.end(), compare);
int minDays = 0;
vector<bool> used(n + 1, false);
for (int i = 0; i < m; i++) {
int from = tunnels[i].from;
int to = tunnels[i].to;
int days = tunnels[i].days;
if (!used[from] && !used[to]) {
minDays = max(minDays, days);
used[from] = true;
used[to] = true;
}
}
cout << minDays << endl;
return 0;
}
```
希望对你有帮助!
阅读全文