Reunion

 Coding Problem Keys 

 Reunion 

 Problem Statement 

Shobita is planning for a reunion with her friends. She is very much excited and making all the preparations. She is busy selecting the restaurants and other points for fun and activities. She has selected N such points. There are R restaurants she has selected considering the amount of time they might have. Shobita wants to enjoy it to the maximum extent with her friends and for that, she needs to plan well. She knows the points (U, V) which are directly connected by a road and the travel time T units required to cover the distance between them. These are E roads between these N points.

 Note:  U is not equal to V.

She wants to know the minimum time she will have to spend to reach the nearest restaurant from all the N points so that she can plan accordingly and know what to do with the amount of time she and her friends will have. She is busy with all other preparations and needs your help in calculating the time required. Can you help her?

 Input Format 

The first line of the input consists of two space-separated integers, N and E respectively.

Next E lines each consists of three space-separated integers, U, V, and T.

The next line consists of a single integer denoting the number of Restaurants points, R.

The next line consists of R space-separated integers denoting the points where Restaurants are located.

 Output Format 

Print the N lines with each line denoting the minimum time required to reach the nearest restaurant from that point.

 Constraints 

1 <= N <= 100000

0 <= E <= 100000

0 <= T <= 100000

1 <= U, V <= N

1 <= R <= N

 Sample Test Case 1 

 Input 

3 2

1 2 6

2 3 4

1

3

 Output 

10

4

0

 Time Limit(X):     0.50 Sec(S) For Each Input

 Memory Limit:    512 MB

 Source Limit:       100 KB

 Solution 

 Programming Language: C++ Language 

// Note: ONLY FEW TEST HAS CASES PASSED...
#include<bits/stdc++.h> 
using namespace std; 
int main(){ 
    int n, m, x, y, z; 
    int k; 
    cin >> n >> m; 
    vector<vector<pair<int, int> > > adj(n); 
    for(int i = 0; i < m; i++){ 
        cin >> x >> y >> z; 
        x -= 1; 
        y -= 1; 
        adj[x].push_back({y, z}); 
        adj[y].push_back({x, z}); 
    } 
    cin >> k; 
    map<int, int> cost; 
    for(int i = 0; i < n; i++) 
        cost[i] = 1e8; 
    queue<int> q; 
    for(int i = 0; i < k; i++){ 
        cin >> x; 
        x -= 1; 
        q.push(x); 
        cost[x] = 0; 
    } 
    while(!q.empty()){ 
        int root = q.front(); 
        q.pop(); 
        for(auto child: adj[root]){ 
            if(cost[child.first] > child.second + cost[root]){ 
                cost[child.first] = child.second + cost[root]; 
                q.push(child.first); 
            } 
        } 
    } 
    for(int i = 0; i < n; i++) 
        cout << cost[i] << endl; 
    return 0; 
}

// Published By PKJCODERS

 (Note: Incase If the code doesn't Pass the output kindly comment us with your feedback to help us improvise.)