vhxpffltm   2달 전

백트랙 해서 체크하고 하면서 했는데 답이 안나오네요...ㅠ

7 11
1 2 47
1 3 69
2 4 57
2 5 124
3 4 37
3 5 59
3 6 86
4 6 27
4 7 94
5 7 21
6 7 40
1 7

이 예제는 잘 나오는데 문제예제가 안나와서 도움좀 부탁드립니다

pinch3773   2달 전

이 문제는 최악의 경우 시간 복잡도가 너무 커서 백트래킹으로 풀 수 없습니다. 

다른 알고리즘이 필요합니다. 

Dijkstra 알고리즘을 공부해 보시기 바랍니다. 

그리고 sol 함수의 for 문에서 

모든 정점과 연결 되어 있는지 확인 해야 하기 때문에 

for(i=n;i<=m;++i) 가 아니라 for(i=1;i<=V;++i)으로 해야 합니다.

그리고 ans값을 처음에 10001으로 하면 안됩니다. 비용이 범위가 [0,100000]이고 정점이 [1,1000] 이라서

최악의 경우 거리가 거의 1000000000 이기 때문입니다. 

pinch3773   2달 전

그리고 이 그래프는 양방향성이 아니라 단방향 성이기 때문에

arr[s][e] = g; 

입니다.

arr[s][e] = arr[e][s] = g; 

가 아닙니다. 

vhxpffltm   2달 전

좋은 말씀 감사합니다~~ 다익스트라 공부해서 해 볼께요~~

댓글을 작성하려면 로그인해야 합니다.