SOLVE

LATER

Minimum Valid Path

/

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

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

Initializing Code Editor...