[ 문제 ] : https://www.acmicpc.net/problem/1238
1238번: 파티
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어
www.acmicpc.net
[ 문제 접근 ]
우선 기존에 알던 평범한 최단 경로 문제 풀이가 아님을 느낌.
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] 를 해주고 가장 큰 값을 찾았다.
전체적으로 코드가 깔끔하다.
'PS > BaekJoon' 카테고리의 다른 글
[1924] 2007 - 입출력 ☆☆☆☆ / 복습 ○ (0) | 2021.11.18 |
---|---|
[11404] 플로이드 - 최단 경로 ★☆☆ / 복습 ○ (0) | 2021.11.18 |
[4386_스폐셜 저지] 별자리 만들기 - MST ★★☆☆ / 복습 ○ (0) | 2021.11.14 |
[2610_스페셜 저지] 회의준비 - Floyd-Warshall ★★★☆ / 복습 ○ (0) | 2021.11.13 |
[2623] 음악프로그램 - 위상정렬 ★★☆ / 복습 ○ (0) | 2021.11.13 |