Minimum Valid Path
/

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

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

## This Problem was Asked in

Initializing Code Editor...