社区讨论
这不是板子题吗,我怎么写挂了?
P1547[USACO05MAR] Out of Hay S参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @lzsm9j5r
- 此快照首次捕获于
- 2024/08/14 00:07 2 年前
- 此快照最后确认于
- 2024/08/14 10:33 2 年前
有点懵
CPP#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int>PII;
const int N=1e5+10;
const int inf=0x3f3f3f3f;
struct edge{int v,s;};
vector<edge>e[N];
int dis[N];
void solve()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int a,b,c;
cin>>a>>b>>c;
e[a].push_back({b,c});
e[b].push_back({a,c});
}
int ans=0;
vector<bool>vis(N,false);
auto prim=[&](int x)
{
priority_queue<PII>q;
for(int i=0;i<=n;i++)dis[i]=inf;
dis[x]=0;
q.push({0,x});
while(q.size())
{
auto t=q.top();q.pop();
int u=t.second;
if(vis[u])continue;
vis[u]=true;
if(dis[u]!=inf)ans=max(ans,dis[u]);
for(auto y:e[x])
{
int v=y.v,s=y.s;
if(dis[v]>s)
{
dis[v]=s;
q.push({-dis[v],v});
}
}
}
};
prim(1);
cout<<ans;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
solve();
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...