글 읽기 - 이 문제 다익스트라로 풀면 안되나요???

dudgh9661 3년 전 0

답은 맞게 나오느데 메모리 초과가 납니다.

1. 다익스트라 알고리즘 적용 가능, 단, 메모리를 줄일 방법 생각

2. 다익스트라 알고리즘 적용 불가

둘 중에 고민중입니다 ㅠㅠ 조언 부탁드립니다.

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

#define INF 1000000

using namespace std;

int N;

vector< pair<short,short> > vec[10001];
//int arr[10001][10001] = { 0 };
vector< vector<short> > arr;
/*
 *  트리의 지름 : 모든 경로들 중 가장 긴 것의 길이
 */

//각 정점마다 다익스트라를 이용해서 최단 거리를 구한다.

void init() {
    cin >> N;

    vector<short> tmp(N+1);

    for(int i = 0; i < N+1; i++) {
        arr.push_back(tmp);
    }

    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= N; j++) {
            arr[i][j] = INF;
        }
    }

    for(int i = 1; i <= N; i++) {
        arr[i][i] = 0;
    }

    int from,to,val;
    for(int i = 1; i < N; i++) {
        cin >> from >> to >> val;
        vec[from].push_back({to, val});
        vec[to].push_back({from, val});
    }
}

void dijkstra(int start) {
    priority_queue< pair<int,int>, vector< pair<int,int> >, greater<> > pq;
    pq.push({start, 0});

    while( !pq.empty() ) {
        int current = pq.top().first;
        int curVal = pq.top().second;
        pq.pop();

        if( arr[start][current] < curVal ) continue;

        for(int i = 0; i < vec[current].size(); i++) {
            int next = vec[current][i].first;
            int nextVal = vec[current][i].second;
            int dist = curVal + nextVal;

//            cout << "cur and next : " << current << "," << next << endl;

            if( arr[start][next] > dist ) {
                arr[start][next] = dist;
                pq.push({next, dist});
            }
        }
    }
}

int main() {
    init();
    for(int i = 1; i <= N; i++) {
        dijkstra(i);
    }

//    for(int i = 1; i <= N; i++) {
//        for(int j = 1; j <= N; j++)
//            cout << arr[i][j] << " ";
//        cout << endl;
//    }
//
    int MAX = -100;
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= N; j++) {
            int value = arr[i][j];
            if( value > MAX ) MAX = value;
        }
//        int value = *max_element(arr[i].begin(), arr[i].end());
//        if ( MAX < value ) {
//            MAX = value;
//        }
    }

    cout << MAX << endl;
    return 0;
}