[27008] Checking an Alibi

https://www.acmicpc.net/problem/27008

최단거리 탐색 문제다.

---

풀이 방법

다익스트라 알고리즘으로 접근했다.

헛간을 기준으로 각 노드까지의 최단거리를 구한 뒤, 결과를 탐색하여 구간까지의 최단거리가 M미만이라면 노드에 해당하는 소의 번호를 오름차순으로 출력하였다.

 

들판에는 소가 여러 마리 존재할 수 있다는 점을 고려하지 않아 [틀렸습니다]를 받았다.

 

질문 게시판에 올라온 반례를 통해 알 수 있었고, 해당 부분을 수정하여 정답을 받았다.

---

정답 코드

	import Foundation
	let FPCM = readLine()!.split(separator: " ").map{Int($0)!}
	let F = FPCM[0], P = FPCM[1], C = FPCM[2], M = FPCM[3]
	var map = Array(repeating: [(node:Int, cost:Int)](), count: F)
	for _ in 0..<P{
	let info = readLine()!.split(separator: " ").map{Int($0)!}
	let U = info[0]-1
	let V = info[1]-1
	let C = info[2]
	map[U].append((V,C))
	map[V].append((U,C))
	}
	var cowInTheFarm = Array(repeating: [Int](), count: F)
	for cow in 0..<C{
	let num = Int(readLine()!)!-1
	cowInTheFarm[num].append(cow)
	}
	func dijk(from DEP:Int)->[Int]{
	var q = [(node:Int, cost:Int)]()
	var minCost = Array(repeating: Int.max, count: F)
	minCost[DEP] = 0
	q.append((DEP,0))
	while !q.isEmpty{
	let curr = q.removeLast()
	if curr.cost > minCost[curr.node]{ continue }
	for next in map[curr.node]{
	let newCost = curr.cost + next.cost
	if newCost < minCost[next.node]{
	minCost[next.node] = newCost
	q.append((next.node, newCost))
	}
	}
	q.sort(by: {$0.cost > $1.cost})
	}
	return minCost
	}
	let res = dijk(from: 0)
	var ans = [Int]()
	for i in 0..<F{
	let curr = res[i]
	if curr<=M{
	for cow in cowInTheFarm[i]{
	ans.append(cow+1)
	}
	}
	}
	ans.sort(by: <)
	print(ans.count)
	for cow in ans{
	print(cow)
	}

view raw 127008.swift hosted with ❤ by GitHub

---