가장 가까운 편의점
면접 대비시간 제한2초메모리 제한512 MB
일부 정점은 집 후보, 일부는 편의점으로 표시된 무방향 가중 그래프에서, 가장 가까운 편의점까지의 최단 경로 거리가 최소인 집 후보를 고르고, 거리가 같으면 정점 번호가 작은 쪽을 고른다.
문제
영선이가 이사할 집을 알아보고 있다. 혼자 살아서 끼니를 편의점에서 해결하는 날이 많으므로, 편의점까지의 거리가 가장 가까운 집을 고르려고 한다.
이사할 도시는 정점과 간선으로 나타낸다. 집 후보와 편의점은 모두 정점 위에 있다. 어떤 집 후보에서 편의점까지의 거리는 그 후보에서 가장 가까운 편의점까지의 최단 거리다.
영선이는 캠프 강사 준비로 바쁘니 대신 집을 골라 주자. 거리가 같은 후보가 여럿이면 정점 번호가 가장 작은 후보를 고른다.
입력
첫째 줄에 정점의 개수 과 간선의 개수 이 주어진다. (, )
다음 개 줄에 각각 , , 가 주어진다. 정점 와 정점 를 잇는 간선의 길이가 라는 뜻이다. (, ) 같은 두 정점을 잇는 간선이 여러 개일 수 있고, 와 가 같은 간선도 있을 수 있다. 간선에는 방향이 없다.
다음 줄에 집 후보의 개수 와 편의점의 개수 가 주어진다. (, , )
다음 줄에 집 후보의 정점 번호가 개, 그다음 줄에 편의점의 정점 번호가 개 주어진다. 한 줄 안에서 같은 번호는 두 번 나오지 않고, 집 후보와 편의점은 서로 겹치지 않는다.
어떤 편의점에도 도달하지 못하는 집 후보가 있을 수 있다. 그런 후보는 고르지 않는다. 편의점에 도달할 수 있는 집 후보는 적어도 하나 있다.
출력
편의점까지의 거리가 가장 가까운 집 후보의 정점 번호를 한 줄에 출력한다. 거리가 같은 후보가 여럿이면 정점 번호가 가장 작은 후보를 출력한다.