파티

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	32979	16381	10904	47.728%

문제

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.

어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다.

이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 T_i(1 ≤ T_i ≤ 100)의 시간을 소비한다.

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

하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.

이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다.

N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다.

두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 T_i가 들어온다.

시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.

모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.

출력

첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.

예제 입력 1

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

예제 출력 1

10

출처

Olympiad > USA Computing Olympiad > 2006-2007 Season > USACO February 2007 Contest > Silver 3번

• 문제를 번역한 사람: author6
• 빠진 조건을 찾은 사람: his130

알고리즘 분류

• 그래프 이론
• 데이크스트라

---

통과된 코드

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

using namespace std;

constexpr int MAXN = 1001;
constexpr int INF = INT32_MAX;

// N : 마을의 수, M : 단방향 도로의 개수, X : 파티의 위치
int N, M, X;

// U : 현재 노드, V : 이웃 노드, dist : 거리
int U, V, dist;

int cnt = 1;

bool debug = false;

int result[MAXN];

/*
각 노드에 연결되어 있는 노드에 대한 정보를 담는 벡터
a번 노드에서 b번 노드로 가는 비용이 c라는 의미
graph[a].push_back((make_pair(B, C));
*/
vector<pair<int, int>> graph[MAXN];

// dist[i][j]  => i 에서 j 까지의 최단거리 (임시 노드)
int disArr[MAXN][MAXN];

// 우선 순위 큐는
// 임시 거리를 가진 노드를 효율적으로 선택하는 데 사용
// <거리, 노드 인덱스>
priority_queue<pair<int, int>> myPQ;

int main()
{
    ios_base::sync_with_stdio(false); // scanf와 동기화를 비활성화
    // cin.tie(null); 코드는 cin과 cout의 묶음을 풀어줍니다.
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> M >> X;
    
    // 간선 입력받기
    for (int i = 0; i < M; i++) {
        cin >> U >> V >> dist;
        graph[U].push_back(make_pair(V, dist));
    } 

    while (cnt <= N) {

        // 임시배열 초기화
        for (int i = 1; i <= N; i++)    disArr[cnt][i] = INF;
        
        // 우선순위 큐에 삽입.
        myPQ.push({ 0, cnt }); // < first : 거리 , second : 노드 인덱스 >
        disArr[cnt][cnt] = 0; 

        while (!myPQ.empty()) {
            // -를 붙이는 이유는 우선순위 큐를 이용하여 정렬하기 위함이다.
            // (최소힙으로 구현)
            int nCost = -myPQ.top().first;
            int now = myPQ.top().second;
            myPQ.pop();
            // 해당 노드에서 연결된 모든 경로를 확인
            for (int i = 0; i < graph[now].size(); i++) {
                // 0이라면 길이 없다는 의미 continue
                if (graph[now][i].second == 0) continue;
                // disSum = 임시 노드 + 현재 노드에서 i로가는 비용
                int disSum = nCost + graph[now][i].second;
                // 비용이 더 작다면 최단경로 테이블 값을 갱신.
                if (disSum < disArr[cnt][graph[now][i].first]) {
                    // 임시 노드 업데이트
                    disArr[cnt][graph[now][i].first] = disSum;
                    // 우선순위 큐에 (거리, 노드 인덱스) 푸시
                    myPQ.push(make_pair(-disSum, graph[now][i].first));
                }
            }
        }

        cnt++;
    }

    if (debug) {
        for (int j = 1; j <= N; j++) {
            cout << "\n";
            for (int i = 1; i <= N; i++) {
                cout << j << " -> " << i << " 의 최소 거리 " << disArr[j][i] << " \n";
            }
            cout << "\n";
        }
    }


    for (int i = 1; i <= N; i++) {
        result[i] = disArr[X][i] + disArr[i][X];
        result[0] = max(result[i], result[0]);
    }

    cout << result[0];

	return 0;
}

배열의 최댓값 MAXN을 101로 두어서 발생한 OutOfBounds 오류

추가적인 아이디어로는

정점들의 정보를 입력 받을 때 역방향 간선을 따로 입력을 받으면

역방향으로 입력을 받으면 각 정점들(A)에서 X로 가는 최단거리를 X->A 최단거리로 바꿀 수 있다.

다익스트라 한 번이면 각 정점들에서 X로 가는 최단거리배열을 구할 수 있다는 것이다. (시간 차이가 엄청남)

https://hyeo-noo.tistory.com/138 <- 참고