Path Value

3.5

4 votes
Problem

Given a connected graph G with N nodes and M edges (edges are bi-directional). Every node is assigned a value A[i]. We define a value of a simple path as :

  • Value of path = Maximum of (absolute difference between values of adjacent nodes in a path).

A path consists of a sequence of nodes starting with start node S and end node E

  • Su1u2....E is a simple path if all nodes on the path are distinct and  S,u1,u2,...,E are nodes in G.

Given a start node S and end node E, find the minimum possible "value of path" which starts with node S and ends with node E.

Input format

  • First line contains two space-separated integers N M
  • Second line contains two space-separated integers S E
  • Next lines contain two space-separated integers u v, denoting an edge between node u and v
  • Next line contains N space-separated integers denoting values of nodes.

Output format

Print a single integer — minimum possible "value of path" between node S and E.

Constraints

1N105N1M1061S,ENSE1u,vN1A[i]106

 

Sample Input
5 7
2 5
1 2
2 3
3 4
4 5
1 3
1 4
1 5
20 23 21 45 21
Sample Output
2
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

Path : 2315 will give the minimum possible path value = 2.

Remember there can be multiple paths that give the same minimum path value between the start node and end node.

Editor Image

?