다익스트라 알고리즘으로 아무대나 시작해서
현재 번호가 가지는 최소 거리가 현재 가중치보다 작다면 다음 반복문으로 넘어가고
크다면 연결된 엣지 개수 1씩 증가하고 현재 번호에서 다음 번호의 사이 최단 거리를 구해서 푸쉬를 했었는데
이게 틀리네 ㅠㅠ
다익스트라 알고리즘으로 아무대나 시작해서
현재 번호가 가지는 최소 거리가 현재 가중치보다 작다면 다음 반복문으로 넘어가고
크다면 연결된 엣지 개수 1씩 증가하고 현재 번호에서 다음 번호의 사이 최단 거리를 구해서 푸쉬를 했었는데
이게 틀리네 ㅠㅠ
나도 증명은 못했는데 플로이드로 정점간 최단경로 싹다구하고 각 간선 보면서 최단경로보다 더 가중치 큰거 지우고 최단경로랑 길이가 같은 간선은 그 간선을 안쓰는 최단경로가 있으면 지웠음
그게 정답임