재난 대비 도시에는 \(N\) 개의 교차로가 있고, 단방향 도로들로 연결되어 있다. 각 교차로 \(v\) 에는 동시에 통과할 수 있는 인원 한도 \(w_v\) 가 정해져 있다(교차로를 거쳐 가는 사람 수가 \(w_v\) 를 넘을 수 없다). 도로 자체에는 인원 제한이 없다.

출발 교차로 \(S\) 에 모인 사람들을 도착 교차로 \(T\) 로 동시에 최대 몇 명까지 보낼 수 있는지 구하여라. 출발지 \(S\) 와 도착지 \(T\) 를 포함한 모든 교차로에 인원 한도가 적용된다. \(S\) 에서 \(T\) 로 가는 경로가 없거나 어느 한도가 \(0\) 이면 그만큼 적게 보낸다.

• \(2 \le N \le 500\)
• \(0 \le M \le 5000\)
• \(0 \le w_v \le 10^9\)
• \(1 \le u,v \le N\), \(u \ne v\)
• \(1 \le S,T \le N\), \(S \ne T\)
• 같은 \((u,v)\) 도로가 중복될 수 있다

첫 줄에 교차로 수 \(N\), 도로 수 \(M\), 출발 \(S\), 도착 \(T\) 가 주어진다.

둘째 줄에 각 교차로의 인원 한도 \(w_1, \dots, w_N\) 이 주어진다.

이어지는 \(M\) 개의 줄에 도로 \(u\ v\) (방향 \(u\to v\)) 가 주어진다.

동시에 \(S\) 에서 \(T\) 로 보낼 수 있는 최대 인원을 정수 한 줄로 출력한다.

riseoj 작성

출처 Original