题目链接：https://codeforces.com/gym/102392/problem/J
题解&代码：https://blog.csdn.net/z472421519/article/details/103003199
#include #include #include #include #define MAXN 1000005 typedef long long ll; using namespace std; ll ans=0; bool vis[MAXN*2]; int tot,n,st; struct Edge1 { int u,v; ll w; }e[MAXN*2]; struct Edge { int to,next; ll w; }edge[MAXN*2]; int head[MAXN]; void init() { tot=0; memset(head,-1,sizeof(head)); memset(vis,false,sizeof(vis)); } void addedge(int u, int v, int w) { edge[tot].to=v; edge[tot].w=w; edge[tot].next=head[u]; head[u]=tot++; } bool cmp(Edge1 e1, Edge1 e2) { return e1.w<e2.w; } int main() { init(); scanf("%d",&n); for (int i=1;i<=n*(n-1)/2;i++) { scanf("%d%d%lld",&e[i].u,&e[i].v,&e[i].w); } sort(e+1,e+1+n*(n-1)/2,cmp); for (int i=1;i<=n*(n-1)/2;i++) { addedge(e[i].u,e[i].v,e[i].w); addedge(e[i].v,e[i].u,e[i].w); } for (int i=1;i<=n;i++) { for(int j = head[i];~j;j=edge[j].next) { ans += edge[j].w; j = edge[j].next; } } cout << ans << endl; return 0; }
