套路题。两个方法,并查集或者SPFA
,推荐用并查集。
第一个,并查集
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN = 1e5 + 2;
int N, M;
int pre[MAXN];
struct Edge
{
Edge(int _n1, int _n2, int _days) :n1(_n1), n2(_n2), days(_days) {}
int n1, n2, days;
bool operator<(const Edge& e) const
{
return days < e.days;
}
};
vector<Edge> ve;
int f(int x)
{
int f0 = x, f1 = x;
for (; pre[f0] > 0;) f0 = pre[f0];
for (; pre[f1] > 0;)
{
int t = f1;
f1 = pre[f1];
pre[t] = f0;
}
return f0;
}
void u(int n1, int n2)
{
int f1 = f(n1);
int f2 = f(n2);
if (f1 != f2)
{
if (pre[f1] <= pre[f2])
{
pre[f1] += pre[f2];
pre[f2] = f1;
}
else
{
pre[f2] += pre[f1];
pre[f1] = f2;
}
}
}
int main()
{
memset(pre, -1, sizeof pre);
int a, b, c;
scanf("%d%d", &N, &M);
for (int i = 0; i < M; i++)
{
scanf("%d%d%d", &a, &b, &c);
//ve.push_back({ a,b,c }); // 用这个会编译错误的
ve.push_back(Edge(a, b, c));
}
sort(ve.begin(), ve.end());
for (int i = 0; i < ve.size(); i++)
{
u(ve[i].n1, ve[i].n2);
if (f(1) == f(N))
{
printf("%d\n", ve[i].days);
break;
}
}
return 0;
}
第二个,SPFA
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int oo = 1e9;
const int MAXN = 1e5 + 5;
int N, M;
bool inq[MAXN] = { 0 };
int opt[MAXN];
struct Edge
{
Edge(int _from, int _to, int _weight) :from(_from), to(_to), weight(_weight) {}
int from, to;
int weight;
};
vector<Edge> ve;
vector<int> v[MAXN];
void bfs(int s)
{
queue<int> q;
q.push(s);
inq[s] = true;
opt[s] = 0;
for (; !q.empty();)
{
int t = q.front();
q.pop();
inq[t] = false;
for (int i = 0; i < v[t].size(); i++)
{
int e = v[t][i];
int next = ve[e].to;
int m;
if ((m = max(opt[t], ve[e].weight)) < opt[next])
{
opt[next] = m;
if (!inq[next])
{
q.push(next);
inq[next] = true;
}
}
}
}
}
int main()
{
scanf("%d%d", &N, &M);
fill(opt + 1, opt + N + 1, oo);
int f, t, w;
for (int i = 0; i < M; i++)
{
scanf("%d%d%d", &f, &t, &w);
ve.push_back(Edge(f, t, w));
ve.push_back(Edge(t, f, w));
v[f].push_back(i << 1);
v[t].push_back(i << 1 | 1);
}
bfs(1);
cout << opt[N] << endl;
return 0;
}
放一个测试用例(样例不行)
6 8
2 3 3
3 6 7
1 4 2
4 5 5
5 6 6
1 2 2
2 4 1
3 5 3
// 6