지름길 건설
시간 제한3초메모리 제한1024 MB
가중치가 있는 도로망에서 각 마을의 가장 가까운 중심 마을과 거리를 유지하면서 추가할 수 있는 바로가기의 최대 개수를 구합니다.
문제
KITPA 나라에는 1부터 까지 번호가 붙은 개의 마을이 있고, 그중 개는 중심 마을이다. 각 마을은 개의 양방향 도로로 다른 마을과 연결되어 있다. 진흥이는 마을 간 교류를 편하게 하기 위해 KITPA 나라에 지름길을 새로 건설하려고 한다.
각 도로에는 길이가 주어져 있으며, 모든 마을에서 다른 모든 마을로 도로만을 통해 이동할 수 있다. 두 마을 사이에는 도로가 많아야 1개 있으며, 두 마을 사이의 거리는 도로만을 통해 이동하는 가장 짧은 경로에 포함된 도로 길이의 합이다. 마을 와 사이의 거리는 이다. 마을 와 중심 마을 사이의 거리가 와 다른 모든 중심 마을 사이의 거리보다 작으면, 는 에 속한다고 한다.
어떤 중심 마을에도 속하지 않는 마을이 있을 수 있다.
진흥이는 두 마을을 골라 그 사이에 도로가 없다면 두 마을을 잇는 지름길을 건설하도록 요청할 수 있다. 이때 지름길이 연결하는 두 마을에 각각 직접 연결된 모든 도로 중 길이가 가장 짧은 도로의 길이보다 지름길의 길이가 짧거나 같아야 KITPA 나라가 건설을 허가한다. 이 기준은 지름길을 하나도 건설하기 전의 도로를 기준으로 한다. 중심 마을끼리는 서로의 세력을 견제하고 있어, 지름길을 건설한 이후에도 다음 조건을 만족해야 한다.
- 지름길을 건설하기 전과 비교해 다른 중심 마을에 속하게 되는 마을이 없어야 한다. 어떤 중심 마을에도 속하지 않는 마을이 새로 생기는 것은 가능하다.
- 각 마을에서 가장 가까운 중심 마을까지의 거리는 지름길을 건설하기 전과 후가 같아야 한다.
진흥이가 조건에 맞게 최대한 많은 지름길을 건설하도록 요청했을 때, KITPA 나라가 건설을 허가하는 지름길의 수를 구하여라.
입력
첫 번째 줄에 마을의 수 , 중심 마을의 수 , 도로의 수 가 주어진다. (; )
두 번째 줄에 중심 마을의 번호 개가 공백으로 구분되어 주어진다. 중심 마을의 번호는 서로 다르다.
세 번째 줄부터 개 줄에 걸쳐 각 줄마다 도로가 연결하는 두 마을의 번호 , 와 도로의 길이 가 공백으로 구분되어 주어진다. (; ; )
출력
진흥이가 조건에 맞게 최대한 많은 지름길을 건설하도록 요청했을 때, KITPA 나라가 건설을 허가하는 지름길의 수를 출력한다.