백준 1238번 : 파티 - 다익스트라 알고리즘 활용 문제

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

1238번: 파티

문제 내용에서

 

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 

 

 

1번 노드에 있는 사람은2번 노드를 거쳤다가 

다시 1번노드로 돌아와야 한다.

 

이 거리를 구해주기 위해 각각의 노드에서 2번 노드까지 가는데 필요한 거리와

 

2번노드에서 각각의 노드에 가는데 필요한 거리를 더해주면 된다.

#include <bits/stdc++.h>

using namespace std;

struct Edge{
	int node, cost;
	Edge(int a, int b){
		node = a;
		cost = b;
	}
	bool operator<(const Edge &b) const{
		return cost > b.cost;
	}
};

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n, m, x, i, a,b,c,j,k;
	scanf("%d %d %d",&n,&m,&x);
	vector<pair<int, int> > map[n+1];

	vector<int> dist2(n+1, INT_MAX); 
	vector<int> ans(n+1, 0);
	priority_queue<Edge> Q;

	for(i=0; i<m; i++){
		scanf("%d %d %d",&a,&b,&c);
		map[a].push_back(make_pair(b,c));
	}

	for(i=1; i<=n; i++){
		Q.push(Edge(i,0));
		dist2[i] = 0;
		while(!Q.empty()){
			int cur_node = Q.top().node;
			int cur_dist = Q.top().cost;
		
			Q.pop();
		
			if(dist2[cur_node] < cur_dist) continue;
				for(j=0; j<map[cur_node].size();j++){
				int next_node = map[cur_node][j].first;
				int next_dist = map[cur_node][j].second;
			
				Q.push(Edge(next_node, cur_dist+next_dist));
				if(dist2[next_node]> cur_dist+next_dist){
					dist2[next_node] = cur_dist+next_dist;
				}
			
			}
		
		}

		if(i==x){
			for(k=1; k<=n; k++){
				ans[k] += dist2[k];
			}
		}
		else{
			ans[i] += dist2[x];
		}
		
		fill(dist2.begin(), dist2.end(), INT_MAX);
		
	}
	
	printf("%d\n", *max_element(ans.begin(),ans.end()));
}