[class4] (백준 1238) 파티

 

 

알고리즘

다익스트라, 우선순위 큐

 

 

[문제 본문]

문제

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.

어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 T_i(1 ≤ T_i ≤ 100)의 시간을 소비한다.

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.

이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 T_i가 들어온다. 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.

모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.

출력

첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.

제한

예제 입력 1

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

예제 출력 1

10

힌트

W3sicHJvYmxlbV9pZCI6IjEyMzgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzMGNcdWQyZjAiLCJkZXNjcmlwdGlvbiI6IjxwPk5cdWFjMWNcdWM3NTggXHVjMjJiXHVjNzkwXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxYyBcdWFjMDFcdWFjMDFcdWM3NTggXHViOWM4XHVjNzQ0XHVjNWQwIFx1ZDU1YyBcdWJhODVcdWM3NTggXHVkNTU5XHVjMGRkXHVjNzc0IFx1YzBiNFx1YWNlMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzViNFx1YjI5MCBcdWIwYTAgXHVjNzc0IE5cdWJhODVcdWM3NTggXHVkNTU5XHVjMGRkXHVjNzc0IFggKDEgJmxlOyZuYnNwO1ggJmxlOyBOKVx1YmM4OCBcdWI5YzhcdWM3NDRcdWM1ZDAgXHViYWE4XHVjNWVjXHVjMTFjIFx1ZDMwY1x1ZDJmMFx1Yjk3YyBcdWJjOGNcdWM3NzRcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LiBcdWM3NzQgXHViOWM4XHVjNzQ0IFx1YzBhY1x1Yzc3NFx1YzVkMFx1YjI5NCBcdWNkMWQgTVx1YWMxY1x1Yzc1OCBcdWIyZThcdWJjMjlcdWQ1YTUgXHViM2M0XHViODVjXHViNGU0XHVjNzc0IFx1Yzc4OFx1YWNlMCBpXHViYzg4XHVjOWY4IFx1YWUzOFx1Yzc0NCBcdWM5YzBcdWIwOThcdWIyOTRcdWIzNzAgVDxzdWI+aTxcL3N1Yj4oMSAmbGU7IFQ8c3ViPmk8XC9zdWI+ICZsZTsgMTAwKVx1Yzc1OCBcdWMyZGNcdWFjMDRcdWM3NDQgXHVjMThjXHViZTQ0XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVkNTU5XHVjMGRkXHViNGU0XHVjNzQwIFx1ZDMwY1x1ZDJmMFx1YzVkMCBcdWNjMzhcdWMxMWRcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YWM3OFx1YzViNFx1YWMwMFx1YzExYyBcdWIyZTRcdWMyZGMgXHVhZGY4XHViNGU0XHVjNzU4IFx1YjljOFx1Yzc0NFx1Yjg1YyBcdWIzY2NcdWM1NDRcdWM2NDBcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MgXHVjNzc0IFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc0MCBcdWM2Y2NcdWIwOTkgXHVhYzhjXHVjNzQ0XHViN2VjXHVjMTFjIFx1Y2Q1Y1x1YjJlOCBcdWMyZGNcdWFjMDRcdWM1ZDAgXHVjNjI0XHVhY2UwIFx1YWMwMFx1YWUzMFx1Yjk3YyBcdWM2ZDBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWIzYzRcdWI4NWNcdWI0ZTRcdWM3NDAgXHViMmU4XHViYzI5XHVkNWE1XHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWM1NDRcdWI5YzggXHVhZGY4XHViNGU0XHVjNzc0IFx1YzYyNFx1YWNlMCBcdWFjMDBcdWIyOTQgXHVhZTM4XHVjNzc0IFx1YjJlNFx1Yjk3Y1x1YzljMFx1YjNjNCBcdWJhYThcdWI5NzhcdWIyZTQuIE5cdWJhODVcdWM3NTggXHVkNTU5XHVjMGRkXHViNGU0IFx1YzkxMSBcdWM2MjRcdWFjZTAgXHVhYzAwXHViMjk0XHViMzcwIFx1YWMwMFx1YzdhNSBcdWI5Y2VcdWM3NDAgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1YzE4Y1x1YmU0NFx1ZDU1OFx1YjI5NCBcdWQ1NTlcdWMwZGRcdWM3NDAgXHViMjA0XHVhZDZjXHVjNzdjXHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YzVlY1x1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTigxICZsZTsmbmJzcDtOICZsZTsgMSwwMDApLCBNKDEgJmxlOyBNICZsZTsgMTAsMDAwKSwgWFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1Yzc4NVx1YjgyNVx1YjQxY1x1YjJlNC4gXHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgTSsxXHViYzg4XHVjOWY4IFx1YzkwNFx1YWU0Y1x1YzljMCBpXHViYzg4XHVjOWY4IFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWMyZGNcdWM3OTFcdWM4MTAsIFx1YjA1ZFx1YzgxMCwgXHVhZGY4XHViOWFjXHVhY2UwIFx1Yzc3NCBcdWIzYzRcdWI4NWNcdWI5N2MgXHVjOWMwXHViMDk4XHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWMxOGNcdWM2OTRcdWMyZGNcdWFjMDQgVDxzdWI+aTxcL3N1Yj5cdWFjMDAgXHViNGU0XHVjNWI0XHVjNjI4XHViMmU0LiBcdWMyZGNcdWM3OTFcdWM4MTBcdWFjZmMgXHViMDVkXHVjODEwXHVjNzc0IFx1YWMxOVx1Yzc0MCBcdWIzYzRcdWI4NWNcdWIyOTQgXHVjNWM2XHVjNzNjXHViYTcwLCBcdWMyZGNcdWM3OTFcdWM4MTBcdWFjZmMgXHVkNTVjIFx1YjNjNFx1YzJkYyBBXHVjNWQwXHVjMTFjIFx1YjJlNFx1Yjk3OCBcdWIzYzRcdWMyZGMgQlx1Yjg1YyBcdWFjMDBcdWIyOTQgXHViM2M0XHViODVjXHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCBcdWNkNWNcdWIzMDAgMVx1YWMxY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc0MCBcdWM5ZDFcdWM1ZDBcdWMxMWMgWFx1YzVkMCBcdWFjMDhcdWMyMTggXHVjNzg4XHVhY2UwLCBYXHVjNWQwXHVjMTFjIFx1YzlkMVx1YzczY1x1Yjg1YyBcdWIzY2NcdWM1NDRcdWM2MmMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWIzNzBcdWM3NzRcdWQxMzBcdWI5Y2MgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBOXHViYTg1XHVjNzU4IFx1ZDU1OVx1YzBkZFx1YjRlNCBcdWM5MTEgXHVjNjI0XHVhY2UwIFx1YWMwMFx1YjI5NFx1YjM3MCBcdWFjMDBcdWM3YTUgXHVjNjI0XHViNzk4IFx1YWM3OFx1YjlhY1x1YjI5NCBcdWQ1NTlcdWMwZGRcdWM3NTggXHVjMThjXHVjNjk0XHVjMmRjXHVhYzA0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxMjM4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU2lsdmVyIENvdyBQYXJ0eSIsImRlc2NyaXB0aW9uIjoiPHA+T25lIGNvdyBmcm9tIGVhY2ggb2YgTiBmYXJtcyAoMSAmbHQ7PSBOICZsdDs9IDEwMDApIGNvbnZlbmllbnRseSBudW1iZXJlZCAxLi5OIGlzIGdvaW5nIHRvIGF0dGVuZCB0aGUgYmlnIGNvdyBwYXJ0eSB0byBiZSBoZWxkIGF0IGZhcm0gI1ggKDEgJmx0Oz0gWCAmbHQ7PSBOKS4gQSB0b3RhbCBvZiBNICgxICZsdDs9IE0gJmx0Oz0gMTAwLDAwMCkgdW5pZGlyZWN0aW9uYWwgKG9uZS13YXkpIHJvYWRzIGNvbm5lY3RzIHBhaXJzIG9mIGZhcm1zOyByb2FkIGkgcmVxdWlyZXMgVGkgKDEgJmx0Oz0gVGkgJmx0Oz0gMTAwKSB1bml0cyBvZiB0aW1lIHRvIHRyYXZlcnNlLjxcL3A+XHJcblxyXG48cD5FYWNoIGNvdyBtdXN0IHdhbGsgdG8gdGhlIHBhcnR5IGFuZCwgd2hlbiB0aGUgcGFydHkgaXMgb3ZlciwgcmV0dXJuIHRvIGhlciBmYXJtLiBFYWNoIGNvdyBpcyBsYXp5IGFuZCB0aHVzIHBpY2tzIGFuIG9wdGltYWwgcm91dGUgd2l0aCB0aGUgc2hvcnRlc3QgdGltZS4gQSBjb3cmIzM5O3MgcmV0dXJuIHJvdXRlIG1pZ2h0IGJlIGRpZmZlcmVudCBmcm9tIGhlciBvcmlnaW5hbCByb3V0ZSB0byB0aGUgcGFydHkgc2luY2Ugcm9hZHMgYXJlIG9uZS13YXkuPFwvcD5cclxuXHJcbjxwPk9mIGFsbCB0aGUgY293cywgd2hhdCBpcyB0aGUgbG9uZ2VzdCBhbW91bnQgb2YgdGltZSBhIGNvdyBtdXN0IHNwZW5kIHdhbGtpbmcgdG8gdGhlIHBhcnR5IGFuZCBiYWNrPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+KiBMaW5lIDE6IFRocmVlIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycywgcmVzcGVjdGl2ZWx5OiBOLCBNLCBhbmQgWDxcL3A+XHJcblxyXG48cD4qIExpbmVzIDIuLk0rMTogTGluZSBpKzEgZGVzY3JpYmVzIHJvYWQgaSB3aXRoIHRocmVlIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VyczogQWksIEJpLCBhbmQgVGkuIFRoZSBkZXNjcmliZWQgcm9hZCBydW5zIGZyb20gZmFybSBBaSB0byBmYXJtIEJpLCByZXF1aXJpbmcgVGkgdGltZSB1bml0cyB0byB0cmF2ZXJzZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD4qIExpbmUgMTogT25lIGludGVnZXI6IHRoZSBtYXhpbXVtIG9mIHRpbWUgYW55IG9uZSBjb3cgbXVzdCB3YWxrLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

 

[푼 코드]

#include <iostream>
#include <vector>
#include <queue>
#define INF 987654321
using namespace std;
struct Road
{
	int goal;
	int time;
};
int N, M, X;
vector<Road> v[1001];
int d[1001];

int Solved(int start, int goal)
{
	priority_queue<pair<int, int>> pq;

	for (int i = 1; i <= N; i++)
	{
		d[i] = INF;
	}
	d[start] = 0;
	pq.push({ 0,start });

	while (!pq.empty())
	{
		int time = -pq.top().first;
		int current = pq.top().second;
		pq.pop();

		if (d[current] < time) continue;

		for (auto iter = v[current].begin(); iter < v[current].end(); iter++)
		{
			if (time + iter->time < d[iter->goal])
			{
				d[iter->goal] = time + iter->time;
				pq.push({ -(time + iter->time),iter->goal });
			}
		}
	}
	return d[goal];
}

int main()
{
	cin >> N >> M >> X;

	int s, e, t;
	for (int i = 0; i < M; i++)
	{
		bool isFind = false;
		cin >> s >> e >> t;

		for (auto iter = v[s].begin(); iter < v[s].end(); iter++)
		{
			if (iter->goal == e)
			{
				isFind = true;
				if (iter->time > t)
				{
					iter->time = t;
				}
				break;
			}
		}

		if (!isFind)
		{
			v[s].push_back({ e,t });
		}
	}

	int maxNum = 0;

	for (int i = 1; i <= N; i++)
	{
		if (i != X)
		{
			int temp = Solved(i, X) + Solved(X, i);
			if (temp > maxNum && temp < INF)
			{
				maxNum = temp;
			}
		}
	}

	cout << maxNum;

	return 0;
}

 

 

#백준 #알고리즘 #다익스트라알고리즘 #백준1238 #백준파티 #우선순위큐