最小生成树Prim写的代码,交上去全T,但是下了个测试点下来一看没问题,哪位大佬帮忙看下什么问题
测试点#1:
输入:
5 6 4 1
4 2 9997
3 5 9999
1 5 9703
2 3 9998
5 1 10000
2 5 5857
输出:
9997
我的代码:
#include<iostream>
#include<cstring>
#include<limits>
#include<queue>
#define MAXN 10005
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[MAXN][MAXN],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;
}