其实最长的一段边权的最小值不一定在最短路上,裸的板子换一下应该是不行的,你试试用堆优化来做,维护一个点与它相邻的一个点的此值和他们之间的边权值,取最大值就行,然后加入堆里就行,具体的你可以参考别人题解(bushi
by xiao7_Mr_10_ @ 2023-08-09 20:55:24
dij能过
```cpp
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int, int> PII;
const int maxn = 201000;
int n, m, s, t;
int e[maxn], h[maxn], w[maxn], ne[maxn], idx;
int dis[maxn];
bool st[maxn];
void add(int a,int b,int c) {
w[idx] = c;
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
void dij(int x) {
dis[x] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({ 0,x });
while (heap.size()) {
auto t = heap.top();
heap.pop();
int dist = t.first;
int ver = t.second;
if (st[ver]) { continue; }
st[ver] = true;
//cout << ver << endl;
for (int i = h[ver];i != -1;i = ne[i]) {
int j = e[i];
if (w[i] <= dis[j]) {
dis[j] = max(w[i], dist);
//cout << 'd' << endl;
heap.push({ dis[j],j });
}
}
}
}
int main()
{
memset(h, -1, sizeof(h));
memset(dis, 0x3f, sizeof(dis));
cin >> n >> m >> s >> t;
for (int i = 1;i <= m;i++) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
add(b, a, c);
}
dij(s);
/*for (int i = 1;i <= n;i++) {
cout << dis[i] << endl;;
}*/
cout << dis[t];
return 0;
}
```
by lanxian @ 2023-09-05 15:05:00