All Tracks Algorithms Graphs Shortest Path Algorithms Problem

Booze First
Tag(s):

Medium

Problem
Editorial
Analytics

As Jignesh was always debarred from alcohol, this eventually made him an alcohol fanatic. The City in which Jignesh lives has N points and these are connected with M edges of non-negative length. There are B booze shops in the city located at different points. Due to his extreme obsession, he can have a craving irrespective of his position in the city, so he wants to know the distance of the nearest booze shop from every point in the city.

Help Him!!

INPUT

The first line contains two integers N & M respectively.

The next M lines contains three integers u, v and w, denoting that there is an edge of length w between node u and node w.

The next line contain a single integer B, which indicates the number of Booze Shops.

The last line of the input has B space-separated integers, which indicate the position of each Booze Shop.

OUTPUT

N lines, where each line will contain the answer for ith point.

CONSTRAINTS :

1 <= N <= 10^5

0 <= M, w <= 10^5

1 <= u, v, B <= N, u ≠ v, and all B are distinct

Self loops are absent

SAMPLE INPUT
3 2
1 2 4
1 3 5
1
3
SAMPLE OUTPUT
5
9
0
Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

Government College of Engineering & Ceramic Technology

Challenge Name

GCECT Codesprint 2018

OTHER PROBLEMS OF THIS CHALLENGE
通知
View All Notifications

?