[Leetcode,c++] Network Delay Time

[Leetcode,c++] Network Delay Time

728x90

문제

코드

class Solution { public: vector>graph[101]; int d[101]; void dijkstra(int start){ priority_queue>pq; pq.push({0,start}); d[start]=0; while(!pq.empty()){ int dist = -pq.top().first; int now = pq.top().second; pq.pop(); if(d[now]>& times, int n, int k) { for(int i=0; i

풀이

dijkstra 로 구현하였다.

위 그래프의 입출력이 아래와 같을때 출력해야하는 문제는 스타트 지점(k=2) 에서 모든 노드(n=4)까지 가는데 걸리는 시간을 출력하는 것이다.

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2 Output: 2

2에서 1번과 3번까지는 동시에 갈수 있으니 동일하게 1초가 걸린다고 볼 수 있다.

for(int i=1; i<=n; i++){ if(d[i]==1e9) return -1; else ans=max(ans,d[i]); }

코드 마지막의 위 부분을 통해서 해당 노드로 갈 수 없을때는 바로 -1을 return 하였고, 갈 수 있는 경우에는 max(ans,d[i])를 통해 해당 노드까지 걸리는 최고 시간을 정답으로 갱신해주었다.(dijkstra를 실행하면서 출발 노드에서 해당 노드까지 걸리는 시간을 갱신해줬으니)

다만 채점시간이 꽤 오래 걸려서 로직 문제인줄 알았는데 옆에 같이 풀던분이랑 로직이 같아서 뭐지 하고 다시 제출해봤는데, 제출 할때마다 시간이 차이가 나서 그냥 채점서버 문제인걸로 ...

from http://dkswnkk.tistory.com/324 by ccl(A) rewrite - 2021-11-22 18:26:54