[다익스트라] (백준 9370) 미확인 도착지

알고리즘

다익스트라

 

 

[문제 본문]

문제

(취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 출발했다는 것, 그리고 목적지 후보들 중 하나가 그들의 목적지라는 것이다. 그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다. 이상이다. (취익)

어휴! (요란한 옷차림을 했을지도 모를) 듀오가 어디에도 보이지 않는다. 다행히도 당신은 후각이 개만큼 뛰어나다. 이 후각으로 그들이 g와 h 교차로 사이에 있는 도로를 지나갔다는 것을 알아냈다.

이 듀오는 대체 어디로 가고 있는 것일까?

예제 입력의 두 번째 케이스를 시각화한 것이다. 이 듀오는 회색 원에서 두 검은 원 중 하나로 가고 있고 점선으로 표시된 도로에서 냄새를 맡았다. 따라서 그들은 6으로 향하고 있다.

입력

첫 번째 줄에는 테스트 케이스의 T(1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스마다

• 첫 번째 줄에 3개의 정수 n, m, t (2 ≤ n ≤ 2 000, 1 ≤ m ≤ 50 000 and 1 ≤ t ≤ 100)가 주어진다. 각각 교차로, 도로, 목적지 후보의 개수이다.
• 두 번째 줄에 3개의 정수 s, g, h (1 ≤ s, g, h ≤ n)가 주어진다. s는 예술가들의 출발지이고, g, h는 문제 설명에 나와 있다. (g ≠ h)
• 그 다음 m개의 각 줄마다 3개의 정수 a, b, d (1 ≤ a < b ≤ n and 1 ≤ d ≤ 1 000)가 주어진다. a와 b 사이에 길이 d의 양방향 도로가 있다는 뜻이다.
• 그 다음 t개의 각 줄마다 정수 x가 주어지는데, t개의 목적지 후보들을 의미한다. 이 t개의 지점들은 서로 다른 위치이며 모두 s와 같지 않다.

교차로 사이에는 도로가 많아봐야 1개이다. m개의 줄 중에서 g와 h 사이의 도로를 나타낸 것이 존재한다. 또한 이 도로는 목적지 후보들 중 적어도 1개로 향하는 최단 경로의 일부이다.

출력

테스트 케이스마다

• 입력에서 주어진 목적지 후보들 중 불가능한 경우들을 제외한 목적지들을 공백으로 분리시킨 오름차순의 정수들로 출력한다.

제한

예제 입력 1

2
5 4 2
1 2 3
1 2 6
2 3 2
3 4 4
3 5 3
5
4
6 9 2
2 3 1
1 2 1
1 3 3
2 4 4
2 5 5
3 4 3
3 6 2
4 5 4
4 6 3
5 6 7
5
6

예제 출력 1

4 5
6

힌트

W3sicHJvYmxlbV9pZCI6IjkzNzAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJiZjhcdWQ2NTVcdWM3NzggXHViM2M0XHVjYzI5XHVjOWMwIiwiZGVzY3JpcHRpb24iOiI8cD4oXHVjZGU4XHVjNzc1KUIxMDAgXHVjNjk0XHVjNmQwLCBcdWM2OTRcdWI3ODBcdWQ1NWMgXHVjNjM3XHVjYzI4XHViOWJjXHVjNzQ0IFx1ZDU1YyBcdWMxMWNcdWNlZTRcdWMyYTQgXHVjNjA4XHVjMjIwXHVhYzAwJm5ic3A7XHVkNTVjIFx1YzMwZFx1Yzc3NCBcdWQ1NWMgXHViM2M0XHVjMmRjXHVjNzU4IFx1YWM3MFx1YjlhY1x1YjRlNFx1Yzc0NCBcdWM3NzRcdWIzZDlcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWIxMDhcdWM3NTggXHVjNzg0XHViYjM0XHViMjk0IFx1YWRmOFx1YjRlNFx1Yzc3NCBcdWM1YjRcdWI1MTRcdWI4NWMgXHVhYzAwXHVhY2UwIFx1Yzc4OFx1YjI5NFx1YzljMCBcdWM1NGNcdWM1NDRcdWIwYjRcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWM2YjBcdWI5YWNcdWFjMDAgXHVjNTRjXHVjNTQ0XHViMGI4IFx1YWM4M1x1Yzc0MCBcdWFkZjhcdWI0ZTRcdWM3NzQgc1x1YzljMFx1YzgxMFx1YzVkMFx1YzExYyBcdWNkOWNcdWJjMWNcdWQ1ODhcdWIyZTRcdWIyOTQgXHVhYzgzLCBcdWFkZjhcdWI5YWNcdWFjZTAgXHViYWE5XHVjODAxXHVjOWMwIFx1ZDZjNFx1YmNmNFx1YjRlNCBcdWM5MTEgXHVkNTU4XHViMDk4XHVhYzAwIFx1YWRmOFx1YjRlNFx1Yzc1OCBcdWJhYTlcdWM4MDFcdWM5YzBcdWI3N2NcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWFkZjhcdWI0ZTRcdWM3NzQgXHVhZTA5XHVkNTVjIFx1YzBjMVx1ZDY2OVx1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAmbmJzcDtcdWJhYTlcdWM4MDFcdWM5YzBcdWFlNGNcdWM5YzAgXHVjNmIwXHVkNjhjXHVkNTU4XHVjOWMwIFx1YzU0YVx1YWNlMCBcdWNkNWNcdWIyZThcdWFjNzBcdWI5YWNcdWI4NWMmbmJzcDtcdWFjMDggXHVhYzgzXHVjNzc0XHViNzdjIFx1ZDY1NVx1YzJlMFx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHVjMGMxXHVjNzc0XHViMmU0LiAoXHVjZGU4XHVjNzc1KTxcL3A+XHJcblxyXG48cD5cdWM1YjRcdWQ3MzQhJm5ic3A7KFx1YzY5NFx1Yjc4MFx1ZDU1YyBcdWM2MzdcdWNjMjhcdWI5YmNcdWM3NDQgXHVkNTg4XHVjNzQ0XHVjOWMwXHViM2M0IFx1YmFhOFx1Yjk3YykmbmJzcDtcdWI0YzBcdWM2MjRcdWFjMDAgXHVjNWI0XHViNTE0XHVjNWQwXHViM2M0IFx1YmNmNFx1Yzc3NFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1YjJlNFx1ZDU4OVx1ZDc4OFx1YjNjNCBcdWIyZjlcdWMyZTBcdWM3NDAgXHVkNmM0XHVhYzAxXHVjNzc0IFx1YWMxY1x1YjljY1x1ZDA3YyBcdWI2ZjBcdWM1YjRcdWIwOThcdWIyZTQuIFx1Yzc3NCBcdWQ2YzRcdWFjMDFcdWM3M2NcdWI4NWMgXHVhZGY4XHViNGU0XHVjNzc0Jm5ic3A7Z1x1YzY0MCBoIFx1YWQ1MFx1Y2MyOFx1Yjg1YyBcdWMwYWNcdWM3NzRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWM5YzBcdWIwOThcdWFjMTRcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YzU0Y1x1YzU0NFx1YjBjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0IFx1YjRjMFx1YzYyNFx1YjI5NCBcdWIzMDBcdWNjYjQgXHVjNWI0XHViNTE0XHViODVjIFx1YWMwMFx1YWNlMCBcdWM3ODhcdWIyOTQgXHVhYzgzXHVjNzdjXHVhZTRjPzxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2Rlc3RpbmF0aW9uLnBuZ1wiIHN0eWxlPVwiZm9udC1zaXplOm1lZGl1bTsgaGVpZ2h0OjIzMHB4OyB3aWR0aDoyMzZweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWM4MWMgXHVjNzg1XHViODI1XHVjNzU4IFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOTdjIFx1YzJkY1x1YWMwMVx1ZDY1NFx1ZDU1YyBcdWFjODNcdWM3NzRcdWIyZTQuIFx1Yzc3NCBcdWI0YzBcdWM2MjRcdWIyOTQgXHVkNjhjXHVjMGM5IFx1YzZkMFx1YzVkMFx1YzExYyBcdWI0NTAgXHVhYzgwXHVjNzQwIFx1YzZkMCBcdWM5MTEgXHVkNTU4XHViMDk4XHViODVjIFx1YWMwMFx1YWNlMCBcdWM3ODhcdWFjZTAgXHVjODEwXHVjMTIwXHVjNzNjXHViODVjIFx1ZDQ1Y1x1YzJkY1x1YjQxYyBcdWIzYzRcdWI4NWNcdWM1ZDBcdWMxMWMgXHViMGM0XHVjMGM4XHViOTdjIFx1YjllMVx1YzU1OFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjIFx1YWRmOFx1YjRlNFx1Yzc0MCA2XHVjNzNjXHViODVjIFx1ZDVhNVx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFQoMSAmbGU7IFQgJmxlOyAxMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQ8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCAzXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCZuYnNwO24sIG0sIHQgKDIgJmxlOyBuICZsZTsgMiAwMDAsIDEgJmxlOyBtICZsZTsgNTAgMDAwIGFuZCAxICZsZTsgdCAmbGU7IDEwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDFcdWFjMDEgXHVhZDUwXHVjYzI4XHViODVjLCBcdWIzYzRcdWI4NWMsIFx1YmFhOVx1YzgwMVx1YzljMCBcdWQ2YzRcdWJjZjRcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCZuYnNwOzNcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4Jm5ic3A7cywgZywmbmJzcDtoICgxICZsZTsgcywgZywgaCAmbGU7IG4pXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gc1x1YjI5NCBcdWM2MDhcdWMyMjBcdWFjMDBcdWI0ZTRcdWM3NTggXHVjZDljXHViYzFjXHVjOWMwXHVjNzc0XHVhY2UwLCBnLCBoXHViMjk0IFx1YmIzOFx1YzgxYyBcdWMxMjRcdWJhODVcdWM1ZDAgXHViMDk4XHVjNjQwJm5ic3A7XHVjNzg4XHViMmU0LiAoZyAmbmU7IGgpPFwvbGk+XHJcblx0PGxpPlx1YWRmOCBcdWIyZTRcdWM3NGMgbVx1YWMxY1x1Yzc1OCBcdWFjMDEgXHVjOTA0XHViOWM4XHViMmU0IDNcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4Jm5ic3A7YSwgYiwgZCAoMSAmbGU7IGEgJmx0OyBiICZsZTsgbiBhbmQgMSAmbGU7IGQgJmxlOyAxIDAwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBhXHVjNjQwIGIgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YWUzOFx1Yzc3NCBkXHVjNzU4IFx1YzU5MVx1YmMyOVx1ZDVhNSBcdWIzYzRcdWI4NWNcdWFjMDAgXHVjNzg4XHViMmU0XHViMjk0IFx1YjczYlx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVhZGY4IFx1YjJlNFx1Yzc0YyB0XHVhYzFjXHVjNzU4IFx1YWMwMSBcdWM5MDRcdWI5YzhcdWIyZTQgXHVjODE1XHVjMjE4IHhcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0XHViMzcwLCB0XHVhYzFjXHVjNzU4IFx1YmFhOVx1YzgwMVx1YzljMCBcdWQ2YzRcdWJjZjRcdWI0ZTRcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiBcdWM3NzQgdFx1YWMxY1x1Yzc1OCBcdWM5YzBcdWM4MTBcdWI0ZTRcdWM3NDAgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWM3MDRcdWNlNThcdWM3NzRcdWJhNzAgXHViYWE4XHViNDUwJm5ic3A7c1x1YzY0MCBcdWFjMTlcdWM5YzAgXHVjNTRhXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YWQ1MFx1Y2MyOFx1Yjg1YyBcdWMwYWNcdWM3NzRcdWM1ZDBcdWIyOTQgXHViM2M0XHViODVjXHVhYzAwIFx1YjljZVx1YzU0NFx1YmQxMFx1YzU3YyAxXHVhYzFjXHVjNzc0XHViMmU0LiBtXHVhYzFjXHVjNzU4IFx1YzkwNCBcdWM5MTFcdWM1ZDBcdWMxMWMgZ1x1YzY0MCBoIFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWIzYzRcdWI4NWNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4IFx1YWM4M1x1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTQuIFx1YjYxMFx1ZDU1YyBcdWM3NzQgXHViM2M0XHViODVjXHViMjk0IFx1YmFhOVx1YzgwMVx1YzljMCBcdWQ2YzRcdWJjZjRcdWI0ZTQgXHVjOTExIFx1YzgwMVx1YzViNFx1YjNjNCAxXHVhYzFjXHViODVjIFx1ZDVhNVx1ZDU1OFx1YjI5NCBcdWNkNWNcdWIyZTggXHVhY2JkXHViODVjXHVjNzU4IFx1Yzc3Y1x1YmQ4MFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVjNzg1XHViODI1XHVjNWQwXHVjMTFjIFx1YzhmY1x1YzViNFx1YzljNCBcdWJhYTlcdWM4MDFcdWM5YzAgXHVkNmM0XHViY2Y0XHViNGU0IFx1YzkxMSBcdWJkODhcdWFjMDBcdWIyYTVcdWQ1NWMgXHVhY2JkXHVjNmIwXHViNGU0XHVjNzQ0IFx1YzgxY1x1YzY3OFx1ZDU1YyBcdWJhYTlcdWM4MDFcdWM5YzBcdWI0ZTRcdWM3NDQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YmQ4NFx1YjlhY1x1YzJkY1x1ZDBhOCBcdWM2MjRcdWI5ODRcdWNjMjhcdWMyMWNcdWM3NTgmbmJzcDtcdWM4MTVcdWMyMThcdWI0ZTRcdWI4NWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiOTM3MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkRlc3RpbmF0aW9uIFVua25vd24iLCJkZXNjcmlwdGlvbiI6IjxwPllvdSBhcmUgYWdlbnQgQjEwMC4gQSBwYWlyIG9mIHByb21pbmVudGx5IGRyZXNzZWQgY2lyY3VzIGFydGlzdHMgaXMgdHJhdmVsaW5nIG92ZXIgdGhlIHJvYWRzIG9mIHRoZSBjaXR5IGFuZCB5b3VyIG1pc3Npb24gaXMgdG8gXHVmYjAxbmQgb3V0IHdoZXJlIHRoZXkgYXJlIGhlYWRlZC4gQWxsIHdlIGtub3cgaXMgdGhhdCB0aGV5IHN0YXJ0ZWQgYXQgcG9pbnQgcyBhbmQgdGhhdCB0aGV5IGFyZSBoZWFkaW5nIGZvciBvbmUgb2Ygc2V2ZXJhbCBwb3NzaWJsZSBkZXN0aW5hdGlvbnMuIFRoZXkgYXJlIGluIHF1aXRlIGEgaHVycnksIHRob3VnaCwgc28gd2UgYXJlIHN1cmUgdGhleSB3aWxsIG5vdCB0YWtlIGEgZGV0b3VyIHRvIHRoZWlyIGRlc3RpbmF0aW9uLjxcL3A+XHJcblxyXG48cD5BbGFzLCBwcm9taW5lbnRseSBkcmVzc2VkIGFzIHRoZXkgbWF5IGJlLCB0aGUgZHVvIGlzIG5vd2hlcmUgdG8gYmUgc2Vlbi4gRm9ydHVuYXRlbHksIHlvdSBoYXZlIGFuIGV4Y2VwdGlvbmFsIHNlbnNlIG9mIHNtZWxsLiBNb3JlIHNwZWNpXHVmYjAxY2FsbHk6IHlvdXIgbm9zZSB3aWxsIG5ldmVyIGxldCB5b3UgZG93bi4gWW91IGNhbiBhY3R1YWxseSBzbWVsbCB0aGV5IGhhdmUgdHJhdmVsZWQgYWxvbmcgdGhlIHJvYWQgYmV0d2VlbiBpbnRlcnNlY3Rpb25zIGcgYW5kIGguPFwvcD5cclxuXHJcbjxwPldoZXJlIGlzIHRoZSBlbHVzaXZlIGR1byBoZWFkZWQ/IE9yIGFyZSB3ZSBzdGlsbCBub3Qgc3VyZT88XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9kZXN0aW5hdGlvbi5wbmdcIiBzdHlsZT1cImhlaWdodDoyMzBweDsgd2lkdGg6MjM2cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+QSB2aXN1YWwgcmVwcmVzZW50YXRpb24gb2YgdGhlIHNlY29uZCBzYW1wbGUuIFRoZSBkdW8gaXMgdHJhdmVsbGluZyBmcm9tIHRoZSBncmF5IGNpcmNsZSB0byBvbmUgb2YgdGhlIHR3byBibGFjayBjaXJjbGVzLCBhbmQgeW91IHNtZWxsZWQgdGhlbSBvbiB0aGUgZGFzaGVkIGxpbmUsIHNvIHRoZXkgY291bGQgYmUgaGVhZGluZyB0byA2LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+T24gdGhlIFx1ZmIwMXJzdCBsaW5lIG9uZSBwb3NpdGl2ZSBudW1iZXI6IHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcywgYXQgbW9zdCAxMDAuIEFmdGVyIHRoYXQgcGVyIHRlc3QgY2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5PbmUgbGluZSB3aXRoIHRocmVlIHNwYWNlLXNlcGVyYXRlZCBpbnRlZ2VycyBuLCBtIGFuZCB0ICgyICZsZTsgbiAmbGU7IDIgMDAwLCAxICZsZTsgbSAmbGU7IDUwIDAwMCBhbmQgMSAmbGU7IHQgJmxlOyAxMDApOiB0aGUgbnVtYmVyIG9mIGludGVyc2VjdGlvbnMgaW4gdGhlIGNpdHksIHRoZSBudW1iZXIgb2YgaW5kaXZpZHVhbCByb2FkcyBiZXR3ZWVuIHRob3NlIGludGVyc2VjdGlvbnMsIGFuZCB0aGUgbnVtYmVyIG9mIHBvc3NpYmxlIGRlc3RpbmF0aW9ucyByZXNwZWN0aXZlbHkuPFwvbGk+XHJcblx0PGxpPk9uZSBsaW5lIHdpdGggdGhyZWUgc3BhY2Utc2VwZXJhdGVkIGludGVnZXJzIHMsIGcgYW5kIGggKDEgJmxlOyBzLCBnLCBoICZsZTsgbik6IHRoZSBpbnRlcnNlY3Rpb24gdGhlIGR1byBzdGFydGVkIGZyb20gYW5kIHRoZSB0d28gaW50ZXJzZWN0aW9ucyBiZXR3ZWVuIHdoaWNoIHRoZSBkdW8gaGFzIHRyYXZlbGVkLCB3aXRoIGcgJm5lOyBoLjxcL2xpPlxyXG5cdDxsaT5tIGxpbmVzIHdpdGggdGhyZWUgc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzIGEsIGIgYW5kIGQgKDEgJmxlOyBhICZsdDsgYiAmbGU7IG4gYW5kIDEgJmxlOyBkICZsZTsgMSAwMDApLCBpbmRpY2F0aW5nIHRoYXQgdGhlcmUgaXMgYSBiaWRpcmVjdGlvbmFsIHJvYWQgYmV0d2VlbiBpbnRlcnNlY3Rpb25zIGEgYW5kIGIgb2YgbGVuZ3RoIGQuPFwvbGk+XHJcblx0PGxpPnQgbGluZXMgd2l0aCBvbmUgaW50ZWdlciB4ICgxICZsZTsgeCAmbGU7IG4pOiB0aGUgcG9zc2libGUgZGVzdGluYXRpb25zLiBBbGwgcG9zc2libGUgZGVzdGluYXRpb25zIGFyZSBkaXN0aW5jdCBhbmQgdGhleSBhcmUgYWxsIGRpZmZlcmVudCBmcm9tIHMuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+VGhlcmUgaXMgYXQgbW9zdCBvbmUgcm9hZCBiZXR3ZWVuIGEgcGFpciBvZiBpbnRlcnNlY3Rpb25zLiBPbmUgb2YgdGhlIG0gbGluZXMgZGVzY3JpYmVzIHRoZSByb2FkIGJldHdlZW4gZyBhbmQgaC4gVGhpcyByb2FkIGlzIGd1YXJhbnRlZWQgdG8gYmUgb24gYSBzaG9ydGVzdCBwYXRoIHRvIGF0IGxlYXN0IG9uZSBvZiB0aGUgcG9zc2libGUgZGVzdGluYXRpb25zLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlBlciB0ZXN0IGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+T25lIGxpbmUgd2l0aCBvbmUgb3IgbW9yZSBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMsIGluZGljYXRpbmcgdGhlIGRlc3RpbmF0aW9ucyB0aGF0IHRoZSBkdW8gY2FuIHN0aWxsIGJlIGhlYWRlZCBmb3IsIGluIGluY3JlYXNpbmcgb3JkZXIuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

 

[푼 코드]

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define MAXNUM 2001
#define INF 987654321
using namespace std;

int n, m, t;
int s, g, h;
vector<pair<int, int>> v[MAXNUM];
vector<int> goal;
int dp[MAXNUM];
void Solved(int start)
{
	for (int i = 1; i <= n; i++)
	{
		dp[i] = INF;
	}
	priority_queue<pair<int, int>> pq;
	dp[start] = 0;
	pq.push({ 0,start });

	while (!pq.empty())
	{
		int cost = -pq.top().first;
		int cur = pq.top().second;
		pq.pop();
		for (auto iter = v[cur].begin(); iter < v[cur].end(); iter++)
		{
			int i_cost = iter->second;
			int i_cur = iter->first;

			if (dp[i_cur] > dp[cur] + i_cost)
			{
				dp[i_cur] = dp[cur] + i_cost;
				pq.push({ -dp[i_cur],i_cur });
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie();
	cout.tie();

	int tc;
	int a, b, d;
	int temp;
	cin >> tc;
	while (tc-- > 0)
	{
		cin >> n >> m >> t;
		cin >> s >> g >> h;

		int mustgoLen = 0;
		for (int i = 0; i < m; i++)
		{
			cin >> a >> b >> d;
			v[a].push_back({ b,d });
			v[b].push_back({ a,d });
			if (a == g && b == h || b == g && a == h)
			{
				mustgoLen = d;
			}
		}

		goal.clear();
		for (int i = 0; i < t; i++)
		{
			cin >> temp;

			Solved(s);
			int minRoot = dp[temp];
			int goG = dp[g] + mustgoLen;
			int goH = dp[h] + mustgoLen;

			Solved(h);
			goG += dp[temp];
			Solved(g);
			goH += dp[temp];

			if (goG <= minRoot || goH <= minRoot)
			{
				goal.push_back(temp);
			}
		}
		sort(goal.begin(), goal.end());
		for (auto iter = goal.begin(); iter < goal.end(); iter++)
		{
			cout << *iter << " ";
		}
		cout << "\n";
		for (int i = 1; i <= n; i++)
		{
			v[i].clear();
		}
	}

	return 0;
}

 

 

#다익스트라 #알고리즘 #백준 #백준9370 #백준미확인도착지