All Tracks Algorithms Graphs Graph Representation Problem

Minimum Valid Path

Algorithms, Dijkstra's algorithm, Graph, Graph Representation


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

4 4
1 2 1
2 3 1
3 4 1
1 3 1
1 4

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

Best Submission

Similar Problems


This Problem was Asked in

Initializing Code Editor...
View All Notifications