[1238] 파티 - 최단 경로 ★☆☆ / 복습 ○

[ 문제 ] : https://www.acmicpc.net/problem/1238

1238번: 파티

---

[ 문제 접근 ]

​

우선 기존에 알던 평범한 최단 경로 문제 풀이가 아님을 느낌.

1. 시작점에서 --> 파티장 / 2. 파티장 에서 --> 시작점 의 합을 모든 노드에 대해서 구해야됨.

​

우선 파티장에서 --> 시작점( 모든 노드 ) 로 오는 건 전형적인 Dijkstra ( one to all ) 문제.

하지만 문제는 시작점에서 --> 파티장 인데 이것도 사실 Dijkstra 로 해결 가능.

 

for (int i = 1; i <= n; i++) { // 모든 노드에 대해서
	Dijkstra(i);
}

 

모든 노드 들에 대해서 Dijkstra 해주면 됨.

​

근데 이렇게 하면 너무 비효율적임. ( Key Point 에서 해결 방법 설명 )

---

[ 최종 코드 ]

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

using std::cout; using std::cin;
using std::vector; using std::pair;

int N, M, X;
const int INF = 987654321;
vector<pair<int, int>> graph[1001];
int d[1001][1001];


struct cmp {
	bool operator()(std::pair<int, int> a, std::pair<int, int> b) {
		return a.second > b.second;
	}
};

void dijkstra(int start,int dest) {
	std::priority_queue<pair<int, int>,vector<pair<int,int>>,cmp> que;
	
	d[start][start] = 0; // 시작 노드 초기화.
	que.push({ start,d[start][start] });

	while (!que.empty()) {
		int cur = que.top().first;
		int cur_dist = que.top().second;
		que.pop();

		if (d[start][cur] < cur_dist) continue; // 이미 갱신됐다면 continue; 
		if (cur == dest && start !=dest) return; // 목적 노드에 도달했으면 stop. 반면에 목적노드에서 출발하는 경우, 끝까지 계산.

		// relaxation
		for (size_t i= 0; i < graph[cur].size(); i++) {
			int next = graph[cur][i].first;
			int next_dist = graph[cur][i].second;

			if (d[start][next] >= d[start][cur] + next_dist) {
				d[start][next] = d[start][cur] + next_dist;
				que.push({ next,d[start][next] });	
			}
		}
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> N >> M >> X;
	while (M--) {
		int a, b, c;
		cin >> a >> b >> c;
		graph[a].push_back({ b,c });
	}
	// 거리 배열 초기화.
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			d[i][j] = INF;
		}
	}
	//  all to one
	for (int i = 1; i <= N; i++) {
		dijkstra(i,X);
	}	

	// 가장 큰 값 찾기
	int max = 0;
	for (int i = 1; i <= N; i++) {

		max = std::max(max, d[i][X]+d[X][i]);
	}
	cout << max;
	


	return 0;
}

---

[ Key Point ]

 

👉 출발 노드에서 모든 노드로 도착하는 최단 경로를 전부 안구해줘도 된다.

     우리가 원하는건 출발 노드에서 부터 파티장 까지의 최단 경로!!

 

그래서 아래처럼 중간에 X 에 도달하면 끝내려고 했는데

 

if (cur == dest) return;

 

문제는 start 가 X 일때는 시작하자마자 종료가 된다. 그래서 조건을 하나 더 넣어준다.

start != dest

 

---

[ 다른 사람 풀이 ▼ ]

 

 

#include <iostream>
#include <limits.h>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

struct edge {
    int end;
    int weight;
    edge(int a, int b) {
        end = a;
        weight = b;
    }
    bool operator<(const edge& e)const {
        return weight > e.weight;
    }
};

int main()
{
    cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);

    int n, m, x;
    cin >> n >> m >> x;

    int s, e, w;
    vector<edge> graph[1001];
    for (int i = 0; i < m; i++) {
        cin >> s >> e >> w;
        graph[s].push_back(edge(e, w));
    }

    vector<vector<int> > dist(n + 1, vector<int>(n + 1, INT_MAX));
    for (int i = 1; i <= n; i++) {
        priority_queue<edge> pQ;
        pQ.push(edge(i, 0));
        dist[i][i] = 0;

        while (!pQ.empty()) {
            e = pQ.top().end;
            w = pQ.top().weight;
            pQ.pop();

            //최단 거리가 정해진 곳은 방문하지 않음
            if (w > dist[i][e]) continue;

            for (auto it = graph[e].begin(); it != graph[e].end(); it++) {
                int a, b;
                a = (*it).end;
                b = (*it).weight;

                if (dist[i][a] > dist[i][e] + b) {
                    dist[i][a] = dist[i][e] + b;
                    pQ.push(edge(a,dist[i][a]));
                }
            }
        }
    }

    int res = 0;
    for (int i = 1; i <= n; i++) {
        res = max(res, dist[x][i] + dist[i][x]);
    }
    cout << res;

    return 0;
}

struct edge 로 받아서 풀었다. ( 역시 이렇게 그래프 받는게 최고인거 같다. )

​

내가 풀었던 거처럼 2차원 배열을 사용하여 dist[x][i] + dist[i][x] 를 해주고 가장 큰 값을 찾았다.

​

전체적으로 코드가  깔끔하다.

 

 

---

 

ref :: https://m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221234427842&proxyReferer=https:%2F%2Fwww.google.com%2F