[C++] BOJ-1238

 

문제풀이

---

1. vector에 단방향 그래프를 입력받는다.

2. 파티에 갈 때와 올 때의 길이 다를 수 있기 때문데 (집 -> 파티), (파티-> 집) 을 따로 다익스트라 알고리즘을 통해 최단경로를 수해야한다.

 

3. 그 경로의 합 중에서 최소를 구한다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int INF = 987654321;

int N,M,X;

vector <pair <int, int> > adj[1001];


int dijkstra(int start, int end){
	vector<int> dist(N,INF);
	dist[start] = 0;
	
	priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > pq;
	pq.push(make_pair(0,start));
	
	while(!pq.empty()){
		int cost = pq.top().first;
		int here = pq.top().second;
		
		pq.pop();
		
		if(dist[here] < cost) continue;
		
		for(int i = 0; i<adj[here].size(); i++){
			int there = adj[here][i].first;
			int nextDist = cost + adj[here][i].second;
			
			if(dist[there] > nextDist){
				dist[there] = nextDist;
				pq.push(make_pair(nextDist,there));
			}
		}
	}
	
	return dist[end];
}

int main(){
	ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M >> X;
	
	N++;
	int arr[N] = {};
	
	for(int i = 0; i<M; i++){
		int a,b,c;
		cin >> a >> b >> c;
		adj[a].push_back(make_pair(b,c));
	}
	
	int go[N] = {};
	
	for(int i = 1; i<N; i++){
		go[i] = dijkstra(i,X) + dijkstra(X,i);
	}

	sort(go, go+N);
	
	cout << go[N-1];
}