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...

## This Problem was Asked in

Challenge Name

May Easy' 19

OTHER PROBLEMS OF THIS CHALLENGE
• Math > Basic Math
• Python > Getting Started
• Algorithms > Dynamic Programming
• Data Structures > Advanced Data Structures
• Data Structures > Advanced Data Structures