만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

지름길 건설

시간 제한3초메모리 제한1024 MB

요약
가중치가 있는 도로망에서 각 마을의 가장 가까운 중심 마을과 거리를 유지하면서 추가할 수 있는 바로가기의 최대 개수를 구합니다.
난이도

어려움10점 중 8점

유형
그래프, 최단 경로, 그리디, 정렬
정답자
아직 제출이 없습니다

문제

KITPA 나라에는 1부터 NN까지 번호가 붙은 NN개의 마을이 있고, 그중 MM개는 중심 마을이다. 각 마을은 KK개의 양방향 도로로 다른 마을과 연결되어 있다. 진흥이는 마을 간 교류를 편하게 하기 위해 KITPA 나라에 지름길을 새로 건설하려고 한다.

각 도로에는 길이가 주어져 있으며, 모든 마을에서 다른 모든 마을로 도로만을 통해 이동할 수 있다. 두 마을 사이에는 도로가 많아야 1개 있으며, 두 마을 사이의 거리는 도로만을 통해 이동하는 가장 짧은 경로에 포함된 도로 길이의 합이다. 마을 AA와 AA 사이의 거리는 00이다. 마을 AA와 중심 마을 BB 사이의 거리가 AA와 다른 모든 중심 마을 사이의 거리보다 작으면, AA는 BB에 속한다고 한다.

어떤 중심 마을에도 속하지 않는 마을이 있을 수 있다.

진흥이는 두 마을을 골라 그 사이에 도로가 없다면 두 마을을 잇는 지름길을 건설하도록 요청할 수 있다. 이때 지름길이 연결하는 두 마을에 각각 직접 연결된 모든 도로 중 길이가 가장 짧은 도로의 길이보다 지름길의 길이가 짧거나 같아야 KITPA 나라가 건설을 허가한다. 이 기준은 지름길을 하나도 건설하기 전의 도로를 기준으로 한다. 중심 마을끼리는 서로의 세력을 견제하고 있어, 지름길을 건설한 이후에도 다음 조건을 만족해야 한다.

  1. 지름길을 건설하기 전과 비교해 다른 중심 마을에 속하게 되는 마을이 없어야 한다. 어떤 중심 마을에도 속하지 않는 마을이 새로 생기는 것은 가능하다.
  2. 각 마을에서 가장 가까운 중심 마을까지의 거리는 지름길을 건설하기 전과 후가 같아야 한다.

진흥이가 조건에 맞게 최대한 많은 지름길을 건설하도록 요청했을 때, KITPA 나라가 건설을 허가하는 지름길의 수를 구하여라.

입력

첫 번째 줄에 마을의 수 NN, 중심 마을의 수 MM, 도로의 수 KK가 주어진다. (2≤M≤N≤100 0002 \le M \le N \le 100\,000; N−1≤K≤200 000N-1 \le K \le 200\,000)

두 번째 줄에 중심 마을의 번호 MM개가 공백으로 구분되어 주어진다. 중심 마을의 번호는 서로 다르다.

세 번째 줄부터 KK개 줄에 걸쳐 각 줄마다 도로가 연결하는 두 마을의 번호 uu, vv와 도로의 길이 ww가 공백으로 구분되어 주어진다. (1≤u,v≤N1 \le u, v \le N; u≠vu \ne v; 1≤w≤1 000 000 0001 \le w \le 1\,000\,000\,000)

출력

진흥이가 조건에 맞게 최대한 많은 지름길을 건설하도록 요청했을 때, KITPA 나라가 건설을 허가하는 지름길의 수를 출력한다.

예제2

  1. 예제 1

    입력
    6 2 10
    2 4
    2 5 5
    4 2 8
    6 4 3
    2 6 9
    5 1 4
    2 3 4
    4 3 6
    1 4 6
    5 4 6
    6 3 7
    
    예상 출력
    4
    
  2. 예제 2

    입력
    8 2 20
    1 4
    4 7 7
    1 6 5
    4 1 1
    6 5 2
    8 2 2
    1 7 8
    5 4 1
    6 8 10
    6 7 6
    3 2 5
    4 6 1
    7 5 5
    3 4 4
    5 8 1
    4 8 5
    3 8 4
    7 8 5
    4 2 8
    1 2 4
    3 5 1
    
    예상 출력
    3