글 읽기 - 어떤 테스트케이스에서 통과가 안되는걸까요?

ugly2003 1년 전 0

X에서 각각 노드로 가는 최단 거리로 N -> X의 최단거리들은 이해가 되는데

그 반대는 어떻게 되는건지 잘 이해가 안되네요 ㅠㅠ

=> 맨 아래 댓글에 수정한 코드에서 4%에서 오류가 뜨네요,,

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

using namespace std;

int INF = 999999;
int DP[1001][1001];
int n, m, x;
int GoBack[1001][2];
bool b = false;
void dijkstra(int start) {
    int min = INF;
    vector<bool> isVisited(n, false);
    vector<int> length(n, INF);
    priority_queue<pair<int, int>, vector<pair<int,int>>, greater<pair<int, int>> > pq;
    //N
    for (int i = 0; i < n; i++) {
        length[i] = DP[start][i];
        pq.push(make_pair(length[i], i));
    }
    isVisited[start] = true;
    //N
    for (int i = 0; i < n; i++) {
        int idx = 0;
        //2 * logN
        idx = pq.top().second;
        pq.pop();
        if (isVisited[idx] == true) continue;
        isVisited[idx] = true;
        //N
        for (int z = 0; z < n; z++) {
            if (isVisited[z] == false) {
                if (length[idx] + DP[idx][z] < length[z]) {
                    length[z] = length[idx] + DP[idx][z];
                    //Fault
                    //Priority Queue에서 가장 가까운 값을 가진 인덱스를 뽑아냄
                    //그래서 만약 갱신이 되었다면, 우선순위 큐에 length[z], z를 넣음
                    //length[z] 새로만들어진 < length[z] (늦게 만들어진) 이기 때문에
                    //항상 새로 만들어진게 먼저 나오게 된다.
                    //그리고 나서 만약 length[z]가 idx로 설정되었을 경우에는,
                    //어차피 isVisited가 true가 되어서 더이상 선정될 이유가 없다.
                    pq.push({ length[z], z }); 
                }
            }
        }
    }

    
    if (b) {
        for (int i = 0; i < n; i++) {
                GoBack[i][0] = length[i];
        }
    }
    else {
        for (int i = 0; i < n; i++) {
                GoBack[i][1] = length[i];
        }
    }
    b = true;
}
int main()
{
    for (int i = 0; i < 1001; i++) {
        for (int k = 0; k < 1001; k++) {
            if (i == k) {
                DP[i][k] = 0;
            }
            else {
                DP[i][k] = INF;
            }
        }
    }
    cin >> n >> m >> x;
    for (int i = 0; i < m; i++) {
        int k, u, p;
        cin >> k >> u >> p;
        DP[k-1][u-1] = p;
    }

    dijkstra(x - 1);
    for (int i = 0; i < 1001; i++) {
        for (int k = 0; k < 1001; k++) {
            int tmp = DP[i][k];
            DP[i][k] = DP[k][i];
            DP[k][i] = tmp;
        }
    }
    dijkstra(x - 1);
    int max = 0;
    for (int i = 0; i < n; i++) {
        if (GoBack[i][0] + GoBack[i][1] > max) {
            max = GoBack[i][0] + GoBack[i][1];
        }
    }
    cout << max;
}

ufshg 1년 전 2

간선이 단방향으로 주어지고,

각 학생은 각각의 집에서 목적지까지 갈수있고, 목적지에서 다시 집으로 돌아올 수 있는 데이터만 주어진다고 명시되어 있습니다.

ugly2003 1년 전 0

바탕으로 수정했는데,

테스트 케이스 다른 블로그 뒤져서 해보아도 4%에서 틀리는데 어디가 잘못된 걸까요?

힌트라도 주시면 감사합니다..

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

using namespace std;

int INF = 999991;
int DP[1001][1001];
int DPR[1001][1001];
int n, m, x;
int GoBack[1001][2];
bool b = false;
void dijkstra(int start) {
    int min = INF;
    vector<bool> isVisited(n, false);
    vector<int> length(n, INF);
    priority_queue<pair<int, int>, vector<pair<int,int>>, greater<pair<int, int>> > pq;
    //length vector
    for (int i = 0; i < n; i++) {
        length[i] = DP[start][i];
        pq.push(make_pair(length[i], i));

    }
    length[start] = true;
    for (int i = 0; i < n; i++) {
      
        int idx = 0;
        int min = INF;
        //Get Minimum Index

        idx = pq.top().second;
        pq.pop();

        isVisited[idx] = true;
        //Update Logic
        for (int z = 0; z < n; z++) {
            if (isVisited[z] == false) {
                if (length[idx] + DP[idx][z] < length[z]) {
                    length[z] = length[idx] + DP[idx][z];
                    pq.push({ length[z], z });
                }
            }
        }

    }

    if (!b) {
        for (int i = 0; i < n; i++) {
            GoBack[i][0] = length[i];
        }
    }
    else {
        for (int i = 0; i < n; i++) {
            GoBack[i][1] = length[i];
        }
    }

}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    //Initialize
    for (int i = 0; i < 1001; i++) {
        for (int k = 0; k < 1001; k++) {
            if (i == k) {
                DP[i][k] = 0;
            }
            else {
                DP[i][k] = INF;
            }
        }
    }
    
    cin >> n >> m >> x;
    for (int i = 0; i < m; i++) {
        int k, u, p;
        cin >> k >> u >> p;
        DP[k-1][u-1] = p;
    }
    int max = -1;
    //N to X;
    dijkstra(x - 1);
    //Inversion
    for (int i = 0; i < n; i++) {
        for (int k = 0; k < n; k++) {
            DPR[k][i] = DP[i][k];
        }
    }
    //Inversion Copy
    for (int i = 0; i < n; i++) {
        for (int k = 0; k < n; k++) {
            DP[i][k] = DPR[i][k];
        }
    }
    b = true;
    dijkstra(x - 1);
    //Find Go and Back Max;
    for (int i = 0; i < n; i++) {
        if (i == x - 1) {
            continue;
        }
        if (max < GoBack[i][0] + GoBack[i][1]) {
            max = GoBack[i][0] + GoBack[i][1];
        }
    }

    cout << max;
}

ugly2003 1년 전 0

ㅠㅠ 외부 포문을 while(!pq.empty())로 바꾸니 해결되었습니다. N회 하는 줄 알았네용..

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

using namespace std;

int INF = 999991;
int DP[1001][1001];
int DPR[1001][1001];
int n, m, x;
int GoBack[1001][2];
bool b = false;
void dijkstra(int start) {
    int min = INF;
    vector<bool> isVisited(n, false);
    vector<int> length(n, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > pq;
    //length vector
    for (int i = 0; i < n; i++) {
        length[i] = DP[start][i];
        pq.push(make_pair(length[i], i));

    }
    isVisited[start] = true;
    while(!pq.empty()){

        int idx = 0;
        int min = INF;
        //Get Minimum Index

        idx = pq.top().second;
        pq.pop();

        if (isVisited[idx] == true) continue;
        isVisited[idx] = true;
        //Update Logic
        for (int z = 0; z < n; z++) {
            if (isVisited[z] == false) {
                if (length[idx] + DP[idx][z] < length[z]) {
                    length[z] = length[idx] + DP[idx][z];
                    pq.push({ length[z], z });
                }
            }
        }

    }

    if (!b) {
        for (int i = 0; i < n; i++) {
            GoBack[i][0] = length[i];
        }
    }
    else {
        for (int i = 0; i < n; i++) {
            GoBack[i][1] = length[i];
        }
    }

}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    //Initialize
    for (int i = 0; i < 1001; i++) {
        for (int k = 0; k < 1001; k++) {
            if (i == k) {
                DP[i][k] = 0;
            }
            else {
                DP[i][k] = INF;
            }
        }
    }

    cin >> n >> m >> x;
    for (int i = 0; i < m; i++) {
        int k, u, p;
        cin >> k >> u >> p;
        DP[k - 1][u - 1] = p;
    }
    int max = -1;
    //N to X;
    dijkstra(x - 1);
    //Inversion
    for (int i = 0; i < n; i++) {
        for (int k = 0; k < n; k++) {
            DPR[k][i] = DP[i][k];
        }
    }
    //Inversion Copy
    for (int i = 0; i < n; i++) {
        for (int k = 0; k < n; k++) {
            DP[i][k] = DPR[i][k];
        }
    }
    b = true;
    dijkstra(x - 1);
    //Find Go and Back Max;
    for (int i = 0; i < n; i++) {
        if (i == x - 1) {
            continue;
        }
        if (max < GoBack[i][0] + GoBack[i][1]) {
            max = GoBack[i][0] + GoBack[i][1];
        }
    }

    cout << max;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어떤 테스트케이스에서 통과가 안되는걸까요?

ugly2003 1년 전 0

ufshg 1년 전 2

ugly2003 1년 전 0

ugly2003 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말