QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#799983 | #8253. Very Important Edge | WeaRD276# | WA | 88ms | 11460kb | C++20 | 1.7kb | 2024-12-05 20:01:45 | 2024-12-05 20:01:46 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define x first
#define y second
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
typedef long long ll;
typedef double db;
typedef long double LD;
typedef pair<int, int> pii;
typedef pair<db, db> pdd;
typedef pair<ll, ll> pll;
const int N = 1e5 + 47;
int par[N];
struct Edge
{
int s, d;
ll w;
Edge(){}
Edge (int ss, int dd, ll ww)
{
s = ss;
d = dd;
w = ww;
}
bool operator<(const Edge& oth)
{
return this->w < oth.w;
}
};
int find_set(int v) {
if (v == par[v])
return v;
return par[v] = find_set(par[v]);
}
bool union_sets(int a, int b) {
a = find_set(a);
b = find_set(b);
if (a != b)
{
par[b] = a;
return true;
}
return false;
}
int solve()
{
int n, m;
if (!(cin >> n >> m))
return 1;
iota(par, par + N, 0);
vector<Edge> ed(m);
FOR (i, 0, m)
{
int v, u;
ll w;
cin >> v >> u >> w;
--v;
--u;
ed[i] = Edge(v, u, w);
}
sort(all(ed));
ed.erase(ed.begin());
ll ans = 0;
FOR (i, 0, m - 1)
{
if (union_sets(ed[i].s, ed[i].d))
ans += ed[i].w;
}
cout << ans << '\n';
return 0;
}
int32_t main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int TET = 1e9;
//cin >> TET;
for (int i = 1; i <= TET; i++)
{
if (solve())
{
break;
}
#ifdef ONPC
cerr << "_____________________________\n";
#endif
}
#ifdef ONPC
cerr << "\nfinished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec\n";
#endif
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 88ms
memory: 11460kb
input:
1000 499500 26 715 732723 850 918 507404 276 643 372190 67 702 972051 397 777 337003 178 185 863117 61 151 943008 83 581 731622 99 501 3260 301 588 948638 17 908 147104 193 480 94512 347 415 416562 519 912 627431 70 959 86892 333 573 757685 129 197 181261 224 636 259176 335 426 567962 193 339 70097 ...
output:
1114260
result:
wrong answer 1st lines differ - expected: '1121154', found: '1114260'