글 읽기 - 이중포문 다익스트라로 풀었는데 지적 부탁드립니다 !

polohee81 4년 전 0

이중포문 다익스트라를 s, g, h로 3번 실행한뒤

( dp[s][g] + dp[g][h] + dp[h][e] ) == dp[s][e]

( dp[s][h] + dp[h][g] + dp[g][e] ) == dp[s][e]

인 경우에 답배열에 추가해준뒤에 정렬한뒤 출력해주었습니다.

실제 대회의 채점케이스를 다운로드받아서 실행해보았는데, 작은 테스트케이스에서는 모두 맞다고 나오는데 직접 그려서

판단할 수 없는 큰 케이스 에서 오답이 발생합니다. 제가 pq로 풀면 풀리는 문제들이 이중포문으로 풀면 종종 오답을 발생하는데, 이문제도 그런 문제중 하나

입니다. 제가 반복문 다익스트라를 구현하는데 있어서 문제가 있는건가요?...

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>
#include <queue>
using namespace std;

int dp[2001][2001];
// vector<int> vec[2001]; pq 다익스트라
vector<int> candidate;
vector<int> ans;
int n, m, t;

void fuc(int start) {
     for (int mid = 1; mid <= n; mid++) {
          for (int end = 1; end <= n; end++) {
               if (dp[start][mid] != INT_MAX && dp[mid][end] != INT_MAX) {
                   dp[start][end] = min(dp[start][end], dp[start][mid] + dp[mid][end]);
               }
          }
     }
}
int main() {
     ios::sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);
     int testCase;

     cin >> testCase;
     for (int test = 1; test <= testCase; test++) {
          ans.clear();
          candidate.clear();
          cin >> n >> m >> t;
         
         // 배열초기화
          for (int i = 1; i <= n; i++) {
               for (int j = 1; j <= n; j++) {
                    if (i == j) dp[i][j] = 0;
                    else dp[i][j] = INT_MAX;
               }
          }
          int s, g, h;
         // s : 시작점, g,h : 거쳐가는 지점
          cin >> s >> g >> h;
          for (int i = 0; i < m; i++) {
               int a, b, d;
               cin >> a >> b >> d;
               dp[a][b] = dp[b][a] = min(dp[a][b], d);
          }
          for (int i = 0; i < t; i++) {
               int tmp; cin >> tmp;
               candidate.push_back(tmp);
          }
        
         // 다익스트라 3번
          fuc(s);
          fuc(g);
          fuc(h);
        
          for (int i = 0; i < candidate.size(); i++) {
               int e = candidate[i];
              
               bool check = false;
               if (dp[s][g] != INT_MAX && dp[g][h] != INT_MAX && dp[h][e] != INT_MAX) {
                    if (dp[s][g] + dp[g][h] + dp[h][e] == dp[s][e]) {
                         ans.push_back(e); 
                         check = true;
                    }
               }
               if (!check) {
                    if (dp[s][h] != INT_MAX && dp[h][g] != INT_MAX && dp[g][e] != INT_MAX) {
                         if (dp[s][h] + dp[h][g] + dp[g][e] == dp[s][e]) {
                              ans.push_back(e);
                         }
                    }
               }
          }

          sort(ans.begin(), ans.end());
          for (const auto & x : ans) {
               cout << x << " ";
          }
          cout << "\n";
     }
}

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

문제

문제

출처

ICPC

이중포문 다익스트라로 풀었는데 지적 부탁드립니다 !

polohee81 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말