CSES - Aalto Competitive Programming 2024 - wk6 - Mon - Results
Submission details
Task:Wide delivery
Sender:arnxxau
Submission time:2024-10-07 17:01:20 +0300
Language:C++ (C++11)
Status:COMPILE ERROR

Compiler report

input/code.cpp: In function 'std::vector<int> widest_path_problem(std::vector<std::vector<std::pair<int, int> > >&, int)':
input/code.cpp:26:42: error: 'INT_MIN' was not declared in this scope
   26 |         vector<int> widest(Graph.size(), INT_MIN);
      |                                          ^~~~~~~
input/code.cpp:4:1: note: 'INT_MIN' is defined in header '<climits>'; did you forget to '#include <climits>'?
    3 | #include <queue>
  +++ |+#include <climits>
    4 | #include <vector>
input/code.cpp:39:23: error: 'INT_MAX' was not declared in this scope
   39 |         widest[src] = INT_MAX;
      |                       ^~~~~~~
input/code.cpp:39:23: note: 'INT_MAX' is defined in header '<climits>'; did you forget to '#include <climits>'?
input/code.cpp: In function 'int main()':
input/code.cpp:84:13: warning: unused variable 'no_vertices' [-Wunused-variable]
   84 |         int no_vertices = 4;
      |             ^~~~~~~~~~~

Code

// C++ implementation of the approach
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

// Function to print the required path
void printpath(vector<int>& parent, int vertex, int target)
{
	if (vertex == 0) {
		return;
	}

	printpath(parent, parent[vertex], target);

	cout << vertex << (vertex == target ? "\n" : "--");
}

// Function to return the maximum weight
// in the widest path of the given graph
vector<int> widest_path_problem(vector<vector<pair<int, int> > >& Graph,
						int src)
{
	// To keep track of widest distance
	vector<int> widest(Graph.size(), INT_MIN);

	// To get the path at the end of the algorithm
	vector<int> parent(Graph.size(), 0);

	// Use of Minimum Priority Queue to keep track minimum
	// widest distance vertex so far in the algorithm
	priority_queue<pair<int, int>, vector<pair<int, int> >,
				greater<pair<int, int> > >
		container;

	container.push(make_pair(0, src));

	widest[src] = INT_MAX;

	while (container.empty() == false) {
		pair<int, int> temp = container.top();

		int current_src = temp.second;

		container.pop();

		for (auto vertex : Graph[current_src]) {

			// Finding the widest distance to the vertex
			// using current_source vertex's widest distance
			// and its widest distance so far
			int distance = max(widest[vertex.second],
							min(widest[current_src], vertex.first));

			// Relaxation of edge and adding into Priority Queue
			if (distance > widest[vertex.second]) {

				// Updating bottle-neck distance
				widest[vertex.second] = distance;

				// To keep track of parent
				parent[vertex.second] = current_src;

				// Adding the relaxed edge in the priority queue
				container.push(make_pair(distance, vertex.second));
			}
		}
	}

	//printpath(parent, target, target);

	return widest;
}

// Driver code
int main()
{

	// Graph representation
	vector<vector<pair<int, int> > > graph;


	int no_vertices = 4;

    int n, m;
    cin >> n >> m;


	graph.assign(n + 1, vector<pair<int, int> >());


    for (int i = 0; i < m; i++)
    {
        int a, b, w;
        cin >> a >> b >> w;
        graph[a].push_back(make_pair(w, b));
        graph[b].push_back(make_pair(w, a));
    }
    

    for (int i = 2; i <= n; i++)
    {
        vector<int> t = widest_path_problem(graph, 1);
        cout << t[i] << ' ';
    }
    cout << endl;
    
	

	return 0;
}