-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
질문있습니다
21.07.31 13:59 작성 조회수 150
0
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
int arr[21];
vector<pair<int,int> > v[21];
int n,m;
void dijstra(int k){
if(k == n){
return;
}
else {
for(int i = 0; i < v[k].size(); i++){
int next = v[k][i].first;
int nextval = v[k][i].second;
if(nextval + arr[k] < arr[next]) arr[next] = nextval + arr[k];
}
dijstra(k+1);
}
}
int main() {
int a,b,c;
scanf("%d %d",&n,&m);
for(int i = 0; i < m; i++){
scanf("%d %d %d",&a,&b,&c);
v[a].push_back(make_pair(b,c)); // 양방향 가중치 그래프
}
for(int i = 1; i <= n; i++){
arr[i] = 2147000000; // 최댓값으로 배열 초기화
}
arr[1] = 0;
dijstra(1);
for(int i = 2; i <= n; i++){
if(arr[i] == 2147000000){
printf("%d : impossible",i);
continue;
}
printf("%d : %d\n",i,arr[i]);
}
return 0;
}
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
제가 직접 짠 코드입니다.
실행하면 문제없이 답이 출력됩니다.
하지만 선생님의 답과 많이 다른데 생각해보니 제 코드가 시간복잡도가 높다고 생각됩니다.
time complexity가 어느정도 차이나는지 궁금합니다!
답변을 작성해보세요.
0
김태원
지식공유자2021.08.03
안녕하세요^^
영상의 다익스트라 방법은 시간복잡도가 NlogN입니다. 위에 코드를 딱 시간복잡도가 뭐다 하기는 저도 애매한데 여튼 재귀를 이용해서 한 코드라 좋아보이지는 않습니다.
영상의 다익스트라 방법을 익혀두시면 좋겠습니다.
답변 1