1. 풀이 (1) 벨만포드를 적용할 때 경로를 저장한다. * 처음엔 특정 노드에서 어디로 가는지를 저장했다. 하지만 이렇게 하면 우리가 원하는 목적지로 가는 경로가 나오는것이 아니라 입력 순서에 영향을 받아 해당 노드에서 어떠한 다른 노드로의 최단경로의 일부가 저장될 수 있다. ex) 1-2, 1,3이 있고 3이 목적지일때 1노드의 방향이 2노드를 향할 수 있다. 따라서 특정 노드가 어느 노드에서 오는지를 저장해야한다. (즉 이전 노드가 무엇인지를) ​ (2) 벨만 포드를 적용한 후 싸이클을 확인해야한다. 이때 경우의 수는 다음과 같다 1. (출발지에 붙은)사이클이 있다 (​isUpdate==True) (1) 도착지와 붙어있다. (q를 통해서 확인, connectCycle==True) => -1 (2) ..

1. 최단거리 2. 최소스패닝 트리(MST)

1.풀이 (1) 목적지에서 벌수있는 돈을 음(-)으로, 이동비용을 (+)로 두고 간선의 가중치를 부여한다 (2) 벨만포드로 최단 거리를 구하기 위해 N-1번 edge relaxation 수행한다. (3) N번째에서 아래의 사항을 확인 - 음의 사이클이 있는지(nodeCost[n1]+cost"gg" - (시작부분과 연결된)음의사이클이 존재하고, 해당 음의 사이클에서 목적지로 이동이가능할때(bfs로확인)->"gee" - 그렇지않은경우(목적지까지 도달할수있고, 음의사이클이 존재하지만 목적지로 도달할수 없는경우 or 음의사이클 존재안하는경우) -> 값출력 (-1곱할것) ​ *많이틀림 처음에 출발지에서 임의의 음의 싸이클까지 연결이 되있는지를 확인해주는 N번째반복의 조건문(nodeCost[n1]!=maxNum)를..