[评测记录](https://www.luogu.com.cn/record/137963551)
by Y_QWQ_Y @ 2023-12-03 10:27:37
@[Y_QWQ_Y](/user/677091)
```cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n, m, s, t, c, h[30001], vis[30001], dis[30001];
priority_queue<pair<int, int>> q;
struct Edge{int nxt, dis, to;}e[30001];
void add (ll from, ll to, ll dis)
{
e[++ c].nxt = h[from];
e[c].dis = to;
e[c].to = dis;
h[from] = c;
}
signed main()
{
scanf ("%d %d %d %d", &n, &m, &s, &t);
for (int i = 0; i < m; ++ i)
{
int u, v, d;
scanf ("%d %d %d", &u, &v, &d);
add (u, v, d);
add (v, u, d);
}
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
dis[s] = 0;
q.push(make_pair(0, s));
while(!q.empty()) {
int x = q.top().second; q.pop();
if(vis[x]) continue;
vis[x] = 1;
for(int i = h[x]; i; i = e[i].nxt) {
int k = max(dis[x], e[i].to), r = e[i].dis;
if(k < dis[r]){
dis[r] = k;
q.push(make_pair(-dis[r], r));
}
}
}
printf ("%d", dis[t]);
return 0;
}
```
by zheng_zx @ 2023-12-03 11:17:00
如果我没有看错的话，你的解法是这样的：
使用链式向前星存储边，并用数组模拟链表；
输入每条边，按无向图处理；
进行 DFS，搜索每个点联通的所有其它的点，直到达到终点；
到达终点时刷新答案；
输出答案；
首先你这个程序有以下几点可以优化：
1. 鉴于输入数据规模不小，可以考虑使用快读
2. 题目“输入格式”中有提到，两个区之间可能存在多条大道，那么我们只需要存储其中拥挤度最小的一条即可，这点可以将链式向前星改成邻接表来方便实现，能够大大降低时间复杂度，能得 40 pts
但是就算把这些优化全部加上也通过不了这一题，我们只能换策略
可用的策略有以下这些：
1. 使用最小生成树（Prim 或 Kruskal 均可）的思想来解决这道题
2. 使用非常玄学的 SPFA 再加上各种优化来解决这道题
3. 使用 Dijkstra + 堆优化来解决这道题
我个人比较推荐最小生成树，因为好理解也好写
我相信你至少会一个（）
by masonxiong @ 2023-12-03 19:09:42
恭喜你猜错了，我都不会，dijkstra还在学，kruskal，spfa都不会
~~本人，卒~~
by Y_QWQ_Y @ 2023-12-03 20:26:30