백준 1238 번 : 파티

문제 접근

---

처음에 바보같이 가장 많은 시간을 소비하는 사람..? 그럼 최장 거리지 하면서 다익스트라로 최장거리를 구하려고 했었다. 다익스트라 알고리즘 그대로 최장 거리 구하려고 하면 양수 사이클 있으니까 당연히 루프 돌텐데 "에..? 왜 루프 돌지..?" 이러고 있었다. 사람인가. 최단 거리 중 가장 긴 값이다.

 

요즘 내가 잘하고 있는건지 모르겠다. 그냥 열심히 하고 있기는 한데 몰두해있는 감각이 느껴지지 않는다. 여기서 잠깐 머리 쉬고 온다고 알고리즘을 안하면 분명 편할거다. 하지만 언제까지고 힘들때마다 기약없이 쉴 수는 없잖아. 계속 흥미를 붙이고 불태우는 연습을 해보자.

 

주의할 점!

1. 문제 조건 똑바로 읽기.

2. 다익스트라에서 단순하게 최장거리를 구현할 때 양수 사이클이 있을 수 있다는 걸 잊지말자.

 

 

문제 코드

---

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

int N, M, X, S, E, T, ans=0;
vector<pair<int,int>> adj[1001];
const int INF = 1000001;

vector<int> longest(int src)
{
	priority_queue<pair<int,int>> q;
	vector<int> dist(N+1, INF);
	
	dist[src] = 0;
	q.push(make_pair(0,src));
	
	while(!q.empty())
	{
		int here = q.top().second;
		int cost = -q.top().first;
		q.pop();
		
		if(dist[here] < cost)
			continue;
		
		for(int i=0; i<adj[here].size(); ++i)
		{
			int there = adj[here][i].second;
			int nextDist = cost + adj[here][i].first;
			
			if(dist[there] > nextDist)
			{
				dist[there] = nextDist;
				q.push(make_pair(-nextDist, there));
				//cout<<"[PUSH] "<<here<<" -> "<<there<<" : "<<nextDist<<'\n';
			}
		}
	}
	
	return dist;
}

int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin>>N>>M>>X;
	
	while(M--)
	{
		cin>>S>>E>>T;
		adj[S].push_back(make_pair(T,E));
	}
	
	vector<int> XtoN = longest(X);
	
	for(int i=1; i<=N; ++i)
	{
		vector<int> NtoX = longest(i);
		ans = max(ans, NtoX[X] + XtoN[i]);
	}
	
	cout<<ans<<'\n';
}