글 읽기 - [ C++ ] 100%에서 틀립니다..

seonbi_g 3년 전 0

안녕하세요, 초보 코딩러입니다.

다름이 아니라, 이 문제 채점시 100%에서 계속 틀립니다.. 이유가 뭔지 도저히 알 수가 없네요 ㅠ

혹시, 제가 어떤 부분에서 실수를 하고 있는지 알 수 있을까요?

저의 문제 풀이 아이디어는 아래와 같습니다.

1. DFS로 최단경로에 포함된 정점을 bool 배열을 이용해서 표시한다.

2. 다익스트라로 S->T로 가는 경로 중 최단 경로에 포함된 정점을 발견하면 무시한다.

와 같은 순서로 진행하였습니다.

어느 부분에서 잘못되었을까요..찜찜하네요 ㅠ

#include<iostream>
#include<queue>
#include<map>
#include<vector>
using namespace std;

#define INF 987654321

typedef pair<int, int> p;

int n, m, s, d, shortestPath = INF;

vector<vector<p>> mm;
vector<int> dist;
vector<bool> stp;


/*
 * dfs 를 통해 최단거리에 존재하는 정점은 true 표시
 * 나중에 다익스트라에서 최단 경로에 포함되는 정점이 발견되는 경우 무시
 */
void dfs(int v, int cost) {
    
    // 정점 V에 연결된 정점들 탐색
    for(auto it = mm[v].begin(); it != mm[v].end(); ++it) {
        int uc = cost + it->first;
        int nv = it->second;

        // 도착지점을 만나고, 이전까지 비용보다 같거나 작으면
        if(nv == d && uc <= dist[nv]) {
            // 비용이 작으면
            if(uc < dist[nv]) {
                // 최단 경로에 포함되는 정점 정보를 초기화
                fill(stp.begin(), stp.end(), false);
                // 최단 경로 비용 갱신
                shortestPath = uc;
            }
            // 현재 위치 최단 경로에 포함
            stp[v] = true;
        }

        // 도착지점이 아니면서, 이전까지 비용보다 작은 경우
        if(uc < dist[nv]) {
            // 최단 거리 갱신
            dist[nv] = uc;
            // DFS 수행
            dfs(nv, uc);
            // 최단 경로 포함 여부 갱신
            stp[v] = stp[v] | stp[nv];
        }
        // 이전까지 비용과 같은 경우
        else if(uc == dist[nv]) {
            // 최단 경로 포함 여부 갱신
            stp[v] = stp[v] | stp[nv];
        }
    }
}




int main() {

    while(1) {

        scanf("%d %d", &n, &m);

        if(n == 0 && m == 0) break;

        scanf("%d %d", &s, &d);

        mm.clear();
        dist.clear(); 
        stp.clear();

        mm.resize(n, vector<p>());
        dist.resize(n, INF);
        stp.resize(n);

        dist[s] = 0;
        shortestPath = INF;

        for (int i = 0; i < m; ++i)
        {
            int sv, ev, cost;
            scanf("%d %d %d", &sv, &ev, &cost);

            mm[sv].push_back({cost, ev});
        }

        // 최단 경로 포함 정점들 확인
        dfs(s, 0);

        // 시작점, 도착점 최단 경로 포함 제외(다익스트라 수행 위함)
        stp[s] = false; 
        stp[d] = false;
        priority_queue<p> pq;
        pq.push({0, s});

        // 최단 거리 테이블 초기화
        fill(dist.begin(), dist.end(), INF);
        dist[s] = 0;

        while(pq.size() > 0) {
            int cost = -pq.top().first;
            int here = pq.top().second;
            pq.pop();

            if(dist[here] < cost) continue;

            for(int i = 0; i < mm[here].size(); ++i) {
                int uc = cost + mm[here][i].first;
                int nv = mm[here][i].second;
                
                // 최단 경로에 포함되는 경우엔 제외
                if(stp[nv]) continue;

                // 다음 정점이 도착 지점이고
                // 최단 경로 비용 < 다음 정점까지 비용 < 현재 비용보다 작은 경우
                // 최단 경로 비용 갱신
                if(nv == d && shortestPath < uc && uc < dist[nv]) {
                    dist[nv] = uc;
                    continue;
                }

                // 다음 정점이 도착 지점이 아니고, 
                // 다음 정점까지의 비용이 갱신된 비용보다 작은경우
                // 탐색 경로에 추가
                if(nv != d && uc < dist[nv]) {
                    dist[nv] = uc;
                    pq.push({-uc, nv});
                }
            }
        }

       // 탐색이 종료되고 도착점까지 올 수 없으면 -1, 도달 가능이면 거리 출력
       printf("%d\n", dist[d] == INF ? -1 : dist[d]);
    }

    return 0;
}

plan222 3년 전 3

최단경로에 포함되는 정점을 전부 패스해버리면 안됩니다.

예외

5 6
0 4
0 1 2
0 2 2
1 2 1
2 4 2
2 3 1
3 4 2

출력: -1
정답: 6

seonbi_g 3년 전 0

감사합니다.. 정점이 아니라 간선을 중점적으로 봐야했는데..

덕분에 기존 코드를 싹 지우고 다시 풀어보니까 풀리네요.. 감사합니다..

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

문제

문제

출처

ICPC

[ C++ ] 100%에서 틀립니다..

seonbi_g 3년 전 0

plan222 3년 전 3

seonbi_g 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말