12 months ago

abzz • 50

Loud Speaker
Problem Description
You have A cities and a array B where B][i][0] and B[i][1] represents there is a road between these cities.
There is another array C containing list of all cities having loudspeakers. A speaker's voice can propagate(travel) through only roads.
All the loudspeakers have some intensities associated with them and it's value is similar for all of them, if the intensity of a speaker is x then it's voice can be heard to all the cities whose shortest distance from this city is less than or equal to x.
A loudspeaker gets automaticlly started if it hears voice from any other loudspeaker. You are given a source city D and a destination city E and there will be always a speaker at source city which someone is starting manually. You have to tell the minumum intensity of the loudspeakers so that the voice reaches to the destination city. See examples for illustrations.
Return -1 if it is impossible.

Problem Constraints
1< A <= 10^5
0 <= |B|<= 10^5
1 <= B[i][0], B[i][[1] <= [A]
1 < ICI <= 10^3
1 < C[i] <= |A|
1 < D < 10^5
1< E < 10^5

 

13 months ago

khush bajaj • 140

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

int minimum_intensity(int A, vector<pair<int, int>> B, vector<int> C, int D, int E) {
    // Initialize distances and intensities
    vector<int> distances(A, INT_MAX);
    distances[D - 1] = 0;
    vector<int> intensities(A, INT_MAX);
    intensities[D - 1] = 0;

    // Create an adjacency list
    vector<vector<pair<int, int>> > adj_list(A);
    for (auto& edge : B) {
        int u = edge.first - 1;
        int v = edge.second - 1;
        adj_list[u].push_back({v, 1}); // Assuming all roads have equal distance of 1
        adj_list[v].push_back({u, 1});
    }

    // Create a priority queue for Dijkstra's algorithm
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, D - 1});

    while (!pq.empty()) {
        int dist = pq.top().first;
        int node = pq.top().second;
        pq.pop();

        if (dist > distances[node]) {
            continue;
        }

        for (auto& neighbor : adj_list[node]) {
            int new_dist = dist + 1;

            if (new_dist < distances[neighbor.first]) {
                distances[neighbor.first] = new_dist;

                // Update intensity for this neighbor
                intensities[neighbor.first] = max(intensities[node], C[neighbor.first]);

                pq.push({new_dist, neighbor.first});
            }
        }
    }

    if (distances[E - 1] == INT_MAX) {
        return -1;
    } else {
        return intensities[E - 1];
    }
}

int main() {
    // Example usage
    int A = 5;
    vector<pair<int, int>> B = {{1, 2}, {2, 3}, {3, 4}, {4, 5}};
    vector<int> C = {10, 20, 30, 40, 50};
    int D = 1;
    int E = 5;

    int result = minimum_intensity(A, B, C, D, E);
    cout << "Minimum intensity: " << result << endl;

    return 0;
}

13 months ago

M any • 20

import heapq

def minimum_intensity(A, B, C, D, E):
    # Initialize distances and intensities
    distances = [float('inf')] * A
    distances[D-1] = 0
    intensities = [float('inf')] * A
    intensities[D-1] = 0

    # Create an adjacency list
    adj_list = [[] for _ in range(A)]
    for u, v in B:
        adj_list[u-1].append((v-1, 1))  # Assuming all roads have equal distance of 1
        adj_list[v-1].append((u-1, 1))

    # Create a priority queue for Dijkstra's algorithm
    pq = [(0, D-1)]

    while pq:
        dist, node = heapq.heappop(pq)

        if dist > distances[node]:
            continue

        for neighbor, _ in adj_list[node]:
            new_dist = dist + 1

            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist

                # Update intensity for this neighbor
                intensities[neighbor] = max(intensities[node], C[neighbor])

                heapq.heappush(pq, (new_dist, neighbor))

    if distances[E-1] == float('inf'):
        return -1
    else:
        return intensities[E-1]

# Example usage
A = 4
B = [(1, 2), (2, 3), (3, 4)]
C = [3, 2, 1, 4]
D = 1
E = 4

result = minimum_intensity(A, B, C, D, E)
print(result)  # Output: 3