[질문] 그래프에서 들려야 되는 노드가 있을때 최소거리 구하는 방법 좀 알려주라

[익명(211.117)]

가중치 및 방향 없음

시작 노드와 마지막 노드 고정

꼭 들려야 되는 노드 리스트가 주어지며 이 리스트를 최소한 한번씩 방문해야함

한 노드에 여러번 들릴 수 있음

위와 같은 조건이 있을때 시작-마지막 노드까지의 최소거리를 구하는 방법이 뭘까

다익스트라로 푸는 것같은데 감이 안 잡히네

코테에서 이거 하나만 못 풀었어 

[익명(210.204)]

제한이 어느 정도인지 모르겠는데, 당장 떠오르는 건 플로이드 와샬 n^3으로 모든 노드간의 최단거리를 구해놓고 꼭 들려야 되는 노드 리스트끼리 bfs 돌리는 거임

[익명(211.117)]

고마워 더 이해 안 되기 시작했어..그래프 개어렵다

[익명(210.204)]

아니다 bfs로는 안 되고 백트래킹 돌려야 겠다

[익명(210.204)]

님아 노드 개수랑 엣지 개수 좀 알려주세요 제발

[익명(211.117)]

문제 조건만 기억해두고 제한 조건은 안 기억해뒀어여..미안합니다..

[익명(122.43)]

모든 점 다 들러야 하는 입력이면 TSP랑 동치라서 안 될듯

[dddd(211.36)]

해커랭크?

[익명(211.117)]

음..말하면 안 되지 않나 유출땜에 노코멘트할게 비슷한 문제 혹시 알면 추천 좀 해주라

[dddd(211.36)]

우리회사건줄 내가 고른 문제일거 같아서

[익명(211.117)]

혹시 회사 이름이 C로 시작함? ㅋㅋㅋ

[dddd(211.36)]

넹

[익명(211.117)]

코가 막힌 우연이네요 맞는듯 글 지워야 되나

[dddd(211.36)]

저는 ㄱㅊ을거같아요 ㅋㅋ

[익명(112.186)]

https://www.acmicpc.net/problem/23840
이거랑 비슷한데?

[익명(211.117)]

고마워 이걸로 공부해야겠다

[익명(223.62)]

들려야하는 노드 개수가 적으면 다익에 비트DP 섞으면 될듯

[익명(halffixednick)]

백트래킹으로 들려야 되는 노드들로 순열 만든 다음에 출발점,노드1,노드2,,,도착점 차례대로 다익스트라 돌리면 시간초과뜨려나

[익명(175.195)]

boj.kr/24888

[익명(118.235)]

왤캐 어렵