@[lgj3475](/user/1062172) 你M用都没用
by aaa_lvzekai @ 2024-02-23 18:38:54
这题不是并查集吗
by sansesantongshun @ 2024-02-23 19:00:43
@[aaa_lvzekai](/user/1055005) 啊对哎，M才是边数，应该是e[M],w[M],ne[M]才对！十分感谢！但改完之后TLE了，感觉其他地方还有问题555
by lgj3475 @ 2024-02-23 20:35:22
@[sansesantongshun](/user/866613) 55我自己试着把并查集的方法打了一遍结果全部MLE了/(ㄒoㄒ)/~~，好滴好滴我看下其他大佬的题解再试试…………
by lgj3475 @ 2024-02-23 20:38:12
@[lgj3475](/user/1062172) 可以不用并查集呀，宽宽我的代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=150010,INF=0x3f3f3f3f3f3f3f3f;
ll n,m,s,t,x,y,z,h[N],w[N],e[N],ne[N],idx,dist[N];
bool vis[N];
priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> heap;
pair<ll,ll> tmp;
void add(ll x,ll y,ll z)
{
w[idx]=z;
e[idx]=y;
ne[idx]=h[x];
h[x]=idx++;
}
void dijkstra(ll s)
{
memset(dist,0x3f,sizeof(dist));
dist[s]=0;
heap.push({0,s});
while(heap.size())
{
tmp=heap.top();
heap.pop();
if(vis[tmp.second])
{
continue;
}
for(int i=h[tmp.second],j;~i;i=ne[i])
{
j=e[i];
if(max(tmp.first,w[i])<dist[j])
{
dist[j]=max(tmp.first,w[i]);
vis[tmp.second]=true;
heap.push({dist[j],j});
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
memset(h,-1,sizeof(h));
cin>>n>>m>>s>>t;
while(m--)
{
cin>>x>>y>>z;
add(x,y,z);
add(y,x,z);
}
dijkstra(s);
cout<<dist[t]<<"\n";
return 0;
}
```
by aaa_lvzekai @ 2024-02-23 21:05:41
@[lgj3475](/user/1062172) 你可以使用cin,cout优化：
```cpp
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
```
by aaa_lvzekai @ 2024-02-23 21:07:22
@[aaa_lvzekai](/user/1055005) orzorzAC了大佬！！！%%%，原来cin、cout可以这样优化，蟹蟹大佬~~
by lgj3475 @ 2024-02-23 21:11:59