93922024-02-21 12:05:00GervidLogisztikai központcpp17Hibás válasz 5/50200ms35348 KiB
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <limits.h>
#include <map>
#include <stack>
#include <algorithm>

using namespace std;

int main() //  !!!borzasztóan megírt kód!!!
{
	int n, i, temp1, temp2, temp3;
	cin >> n;

	vector<vector<pair<int, int>>> g(n);

	for (i = 0; i < n-1; i++)
	{
		cin >> temp1 >> temp2 >> temp3;

		g[--temp1].push_back({ temp3, --temp2 });
		g[temp2].push_back({ temp3, temp1 });
	}

	vector<int> d1(n, INT_MAX), d2(n, INT_MAX), d3(n, INT_MAX);

	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;

	q.push({ 0, 0 });
	d1[0] = 0;

	while (!q.empty())
	{
		int node = q.top().second;
		for (i = 0; i < g[q.top().second].size(); i++)
		{
			int neighbour = g[node][i].second, weight = g[node][i].first;
			if (d1[neighbour] > d1[node] + weight)
			{
				d1[neighbour] = d1[node] + weight;
				q.push({ d1[neighbour], neighbour });
			}
		}
		q.pop();
	}

	int start = 0, maxv = 0;
	for (i = 0; i < n; i++)
	{
		if (d1[i] != INT_MAX && d1[i] > maxv)
		{
			maxv = d1[i];
			start = i;
		}
	}

	q.push({ 0, start });
	d2[start] = 0;

	while (!q.empty())
	{
		int node = q.top().second;
		for (i = 0; i < g[q.top().second].size(); i++)
		{
			int neighbour = g[node][i].second, weight = g[node][i].first;
			if (d2[neighbour] > d2[node] + weight)
			{
				d2[neighbour] = d2[node] + weight;
				q.push({ d1[neighbour], neighbour });
			}
		}
		q.pop();
	}

	start = 0, maxv = 0;
	for (i = 0; i < n; i++)
	{
		if (d2[i] != INT_MAX && d2[i] > maxv)
		{
			maxv = d2[i];
			start = i;
		}
	}

	q.push({ 0, start });
	d3[start] = 0;

	while (!q.empty())
	{
		int node = q.top().second;
		for (i = 0; i < g[q.top().second].size(); i++)
		{
			int neighbour = g[node][i].second, weight = g[node][i].first;
			if (d3[neighbour] > d3[node] + weight)
			{
				d3[neighbour] = d3[node] + weight;
				q.push({ d1[neighbour], neighbour });
			}
		}
		q.pop();
	}

	int min = INT_MAX, distance;
	vector<int> mini;
	for (i = 0; i < n; i++)
	{
		if (max(d2[i], d3[i]) < min)
		{
			min = max(d2[i], d3[i]);
			mini = { i };
			distance = max(d2[i], d3[i]);
		}
		else
		{
			if (max(d2[i], d3[i]) == min)
			{
				mini.push_back(i);
			}
		}
	}
	cout << distance << '\n' << mini.size() << '\n';

	for (i = 0; i < mini.size(); i++)
	{
		cout << mini[i] + 1<< ' ';
	}
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base5/50
1Elfogadva0/03ms1812 KiB
2Hibás válasz0/0126ms17032 KiB
3Elfogadva4/43ms3828 KiB
4Hibás válasz0/43ms4000 KiB
5Hibás válasz0/43ms4220 KiB
6Hibás válasz0/43ms4432 KiB
7Hibás válasz0/43ms4660 KiB
8Hibás válasz0/54ms5060 KiB
9Hibás válasz0/2138ms22524 KiB
10Hibás válasz0/2138ms23472 KiB
11Hibás válasz0/23ms8464 KiB
12Részben helyes1/24ms8688 KiB
13Hibás válasz0/28ms9604 KiB
14Hibás válasz0/214ms10628 KiB
15Hibás válasz0/2130ms24348 KiB
16Hibás válasz0/2103ms25052 KiB
17Hibás válasz0/2136ms28132 KiB
18Hibás válasz0/290ms25636 KiB
19Hibás válasz0/2200ms35348 KiB
20Hibás válasz0/3104ms32232 KiB