你开$10005*10005$的二维邻接矩阵,不$MLE$才怪,$prim$可以直接用结构体存边,或者用链式前向星(邻接表太不方便差重边)
by zhangshirui @ 2024-01-10 14:48:23
@[AZYDLL](/user/881733)
by zhangshirui @ 2024-01-10 14:49:02
@[AZYDLL](/user/881733) 最多给你改成这样:
```cpp
#include<iostream>
#include<cstring>
#include<limits>
#include<queue>
#define MAXN 100005
using namespace std;
struct node {int ed,dis;};
struct cmp
{
bool operator()(node a,node b)
{return b.dis<a.dis;}
};
priority_queue<node,vector<node>,cmp > p_q;
int n,m,s,t,dis[MAXN],vis[MAXN],edge[5005][5005],ans;
int main()
{
int maxn=numeric_limits<int>::max();
memset(edge,-1,sizeof(edge));
cin>>n>>m>>s>>t;
for(int i=1;i<=n;i++) dis[i]=maxn;
for(int i=1;i<=m;i++)
{
int u,v,w;
cin>>u>>v>>w;
edge[u][v]=edge[u][v]==-1 ? w : min(edge[u][v],w);
edge[v][u]=edge[u][v];
}
node a; a.ed=s,a.dis=0;
p_q.push(a);
while(!p_q.empty())
{
node nw=p_q.top();
p_q.pop();
if(vis[nw.ed]==1) continue;
vis[nw.ed]=1,ans=max(ans,nw.dis);
if(nw.ed==t) break;
for(int i=1;i<=n;i++)
{
if(vis[i]==0 && edge[nw.ed][i]!=-1 && edge[nw.ed][i]<dis[i])
{
dis[i]=edge[nw.ed][i];
node a; a.ed=i,a.dis=dis[i];
p_q.push(a);
}
}
}
cout<<ans<<endl;
return 0;
}
```
$\text{edge}$ 数组开小一点
[评测记录](https://www.luogu.com.cn/record/142420971)
by Weekoder @ 2024-01-10 15:07:55
@[AZYDLL](/user/881733) 还有一个点 $\color{purple}\texttt{RE}$ 了,改一下吧
by Weekoder @ 2024-01-10 15:10:03
@[AZYDLL](/user/881733) 可以试试最小生成树+并查集的做法
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;
int n, m, s, t, f[N];
struct node {
int u, v, w;
}e[N * 2];
bool cmp(node x, node y) {
return x.w < y.w;
}
void init() {
for (int i = 1; i <= n; i++)
f[i] = i;
return ;
}
int findf(int i) {
if (f[i] == i)
return i;
return f[i] = findf(f[i]);
}
bool merge(int x, int y) {
int t1 = findf(x), t2 = findf(y);
if (t1 != t2) {
f[t2] = t1;
return 1;
}
return 0;
}
int main() {
cin >> n >> m >> s >> t;
init();
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
e[i].u = u, e[i].v = v, e[i].w = w;
}
sort(e + 1, e + 1 + m, cmp);
int sum = 0, ans = 0;
for (int i = 1; i <= m; i++) {
merge(e[i].u, e[i].v);
if (findf(s) == findf(t)) {
cout << e[i].w;
return 0;
}
}
return 0;
}
```
by Weekoder @ 2024-01-10 15:29:26
@[zhangshirui](/user/1040353) @[Weekoder](/user/800884) 谢谢大佬!我自己再改改
by AZYDLL @ 2024-01-11 12:57:02
此贴结
by AZYDLL @ 2024-01-11 13:41:00