tose33

https://www.acmicpc.net/problem/2157 2157번: 여행 첫째 줄에 N(1 ≤ N ≤ 300), M(2 ≤ M ≤ N), K(1 ≤ K ≤ 100,000)가 주어진다. K는 개설된 항공로의 개수이다. 다음 K개의 줄에는 각 항공로에 대한 정보를 나타내는 세 정수 a, b, c(1 ≤ a, b ≤ N, 1 ≤ c ≤ 1 www.acmicpc.net 이동은 작은번호에서 큰 번호 만 가능하다고 했기 때문에 입력을 받을때 큰번호->작은번호는 저장 자체를 안해주면 된다. 기본적으로 다익스트라처럼 d[i] 에 i번 노드에 도착했을때 먹을수 있는 최대 기내식을 저장하고, 다음 노드로 이동했을때 기내식 점수를 계산해서 d 에 저장되어 있는 점수보다 작다면 이동하지 않으면 된다. 하지만 이 문..

https://www.acmicpc.net/problem/15971 15971번: 두 로봇 2018년 강원도에서 새로운 동굴이 발견되었다. 이 동굴에는 총 N개의 넓은 방이 존재하며 좁은 통로로 서로 연결되어 있는 것으로 밝혀졌다. N개의 방은 1번부터 N번까지의 번호를 붙여 1번 방, 2번 www.acmicpc.net 설명을 보면 주어지는 그래프는 최소 스패닝 트리 (MST) 이다. 그렇다면 하나의 노드에서 다른 노드까지의 경로는 유일하다. 따라서 하나의 로봇에서 다른 로봇까지의 경로를 알아내고, 임의의 통로의 양 끝에 위치한 두 방들도 그 통로 위에 위치해 있다고 간주한다 라고 했으므로 경로중 가장 가중치가 큰 통로의 양끝에서 만나면 된다.

https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 시작 노드에서 다른 노드를 거쳐 다시 시작 노드로 돌아오는 최소 비용을 구하는 문제였다. 플로이드 와샬 알고리즘으로 모든 노드들의 각 최소 거리를 구해서, 시작 노드 a에서 b노드 까지의 최소 거리 + b에서 a노드 까지의 최소 거리중 가장 작은 값을 구하면 된다. 그런데 나는 보통 그냥 다익스트라를 모든 노드에 대하여 돌려서 쓴다. 왜냐하면 대부분의 경우 다익스..

https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 다익스트라 알고리즘을 이용해 시작 컴퓨터에서 시작해서, 방문 가능한 노드들의 수가 총 감염되는 컴퓨터의 수이고, 방문 가능 노드들 중 도달 시간이 가장 큰 시간이 마지막 컴퓨터가 감염되기까지의 시간이다.