代码拉取完成,页面将自动刷新
同步操作将从 charlieshu/Algorithms 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
struct edge{
int s,t,s_next,t_next,len;
bool operator < (const edge a)const{
return len>a.len;
}
};
int main(){
int n,m;
long long ans=0;
bool can_build=true;
cin>>n>>m;
bool vis[n];
memset(vis,false,sizeof(vis));
int edge_header[n];
memset(edge_header,-1,sizeof(edge_header));
edge edges[m];
for(int i=0;i<m;i++){
int s,t,len;
cin>>s>>t>>len;
s--;t--;
edges[i].s = s;
edges[i].t = t;
edges[i].len = len;
edges[i].s_next = edge_header[s];
edges[i].t_next = edge_header[t];
edge_header[s] = edge_header[t] = i;
}
priority_queue<edge> q;
int now=0;
// vis[now] = true;
for(int i=0;i<n-1;i++){
if(!vis[now]){
vis[now] = true;
int next = edge_header[now];
while(next != -1){
if(!(vis[edges[next].s] && vis[edges[next].t]))
q.push(edges[next]);
if(edges[next].s == now)
next = edges[next].s_next;
else
next = edges[next].t_next;
}
}
while(vis[q.top().s] && vis[q.top().t]){ q.pop();}
if(q.empty()){
can_build = false;
break;
}
ans += q.top().len;
if(q.top().s == now){
// vis[q.top().t] = true;
now = q.top().t;
}
else{
// vis[q.top().s] = true;
now = q.top().s;
}
q.pop();
}
if(can_build)
cout<<ans;
else
cout<<"orz";
return 0;
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。