VMCOMP - Công việc tuyển dụng
Tác giả: flashmt
Ngôn ngữ: C++
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
int n, S;
long long sum[100100];
vector <int> a[100100], c[100100];
int main()
{
int m, x, y, z;
cin >> n >> m >> S;
while (m--)
{
scanf("%d%d%d", &x, &y, &z);
a[x].push_back(y); c[x].push_back(z);
a[y].push_back(x); c[y].push_back(z);
sum[x] += z;
sum[y] += z;
}
queue <int> q;
for (int i = 1; i <= n; i++)
if (sum[i] < S) q.push(i);
int ans = n;
while (!q.empty())
{
int x = q.front(); q.pop();
ans--;
for (int i = 0; i < int(a[x].size()); i++)
{
int y = a[x][i];
if (sum[y] >= S)
{
sum[y] -= c[x][i];
if (sum[y] < S) q.push(y);
}
}
}
if (!ans) puts("-1");
else
{
cout << ans << endl;
for (int i = 1; i <= n; i++)
if (sum[i] >= S) printf("%d ", i);
}
}