All Tracks Algorithms Graphs Graph Representation Problem

Minimum Valid Path
Tag(s):

Algorithms, Dijkstra's algorithm, Graph, Graph Representation, Medium

Problem
Editorial
Analytics

You are given a weighted directed graph some of whose vertices are marked as special vertices. A valid path in it is a path which satisfies the following conditions:

1. For any two adjacent edges x and y on the path, 0.5*weight($$x$$) <= weight($$y$$) <= 2*weight($$x$$)

2. The path contains exactly one special vertex.

Given two vertices $$x$$ and $$y$$, your task is to calculate the minimum cost of a valid path between them.


Input Format

First line:  $$n$$ and $$m$$, the number of vertices and the number of edges in the graph.
($$1 \le n \le 10^5$$, $$1 \le m \le 5*10^5$$ )

Next $$m$$ lines contain three integers $$u$$, $$v$$, and $$w$$ representing an edge from vertex $$u$$ to vertex $$v$$, with a weight of e. ($$1 \le u, v \le n$$, $$1 \le w \le 10^9$$)

Next line contains an integer $$k$$ - the number of special vertices. ($$1 \le k \le n$$)

Next line contains $$k$$ distinct integers, the indices of the special vertices. ($$1 \le index \le n$$)

The last line contains the integers $$x$$ and $$y$$, the source and destination vertices.
($$1 \le x, y \le n$$)

Note: Graph can have multiple edges between two vertices.

Output Format

If there is no valid path from $$x$$ to $$y$$ output -1, else output the minimum cost of a valid path from $$x$$ to $$y$$.

SAMPLE INPUT
4 4
1 2 1
2 3 1
3 4 1
1 3 1
1
4
1 4
SAMPLE OUTPUT
2
Explanation

In the given sample, it is clear that path 1-3-4 is a valid path with cost 2. Though 1-2-3-4 is also a valid path, but its cost is 3. So, 2 is the minimum cost of a valid path.

 

Time Limit: 4.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

HackerEarth

Challenge Name

May Easy' 19

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?