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);
	}
}

Download