QAQ大佬竟然谢一个棕名 好感动
by 哔哩哔哩 @ 2018-11-02 16:11:28
我也被卡了T2 & T10
```
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
const int MAXN = 10000 + 10 ,MAXP = 100000 + 10;
int n ,p ,c[MAXN];
int fa[MAXN] ,ans ,road;
inline int read()
{
int x = 0 ,y = 1;
char c = getchar();
while(c > '9' || c < '0')
{
if(c == '-')y = -1;
c = getchar();
}
while(c <= '9' && c >= '0')
{
x = x * 10 + c - '0';
c = getchar();
}
return x * y;
}
struct node
{
int x ,y ,l;
}t[MAXP];
int cmp(node x ,node y)
{
return x.l < y.l;
}
int find(int x)
{
if(fa[x] == x)return x;
else find(fa[x]);
}
void Union(int x ,int y)
{
fa[find(x)] = find(y);
}
void kruskal()
{
sort(t + 1 ,t + 1 + p ,cmp);
for(register int i = 1;i <= n;i++)fa[i] = i;
for(register int i = 1;road < n - 1;i++)
{
if(find(t[i].x) != find(t[i].y))
{
ans += t[i].l;
Union(t[i].x ,t[i].y);
road++;
}
}
}
int main()
{
n = read(); p = read();
for(register int i = 1;i <= n;i++) c[i] = read();
for(register int i = 1;i <= p;i++)
{
t[i].x = read(); t[i].y = read(); t[i].l = read();
t[i].l *= 2;
t[i].l += c[t[i].x] + c[t[i].y];
}
kruskal();
sort(c + 1 ,c + 1 + n);
cout << ans + c[1];
return 0;
}
```
by jbc392 @ 2019-10-09 22:31:09
求救
by jbc392 @ 2019-10-09 22:31:32