[C++] 5719번 거의 최단 경로 - 그래프 이론, 그래프 탐색, 데이크스트라

1. 문제

<입력>

• 각 테스트케이스 첫째 줄 장소의 수 \(N(2 \leq N \leq 500)\)과 도로의 수 \(M(1 \leq M \leq 10^{4})\)가 주어짐.
• 0~N-1까지 장소의 번호가 매겨지는데
• -2-  시작점 S, 도착점 D \((S \neq D, 0 \leq S, D < N)\)
• 다음 M개의 줄 U에서 V로 가는 도로의 길이 P가 주어짐 \((U \neq V; 0 \leq U, V < N; 1 \leq P \leq 10^{3})\)
• U->V 도로는 최대 한 개이며 U->V는 V->U와 다르다.
• 입력의 마지막 줄에는 0이 두 개가 있다.

<출력>

• 각 테스트케이스에 대해 거의 최단 경로 길이를 출력하며 없는 경우에는 -1을 출력하라

2. 재정의

• 최단 경로에 포함되는 도로 제외 최단 경로

3. 해결방법 - 생략

4. 실수한 점, 개선할 점 - 생략

 

<코드>

#include <iostream>
#include <string.h>
#include <queue>
#include <vector>

#define pii pair<int, int>
#define Fi first
#define Se second

const int MAX_N = 501;
const int INF = 987654321;

using namespace std;

int N, M;  //장소의 수 N, 도로의 수 M
int S, D;  //시작점 S, 도착점 D
vector<pii> Vertex[MAX_N];  //그래프
int Dist[MAX_N];  //최단거리
vector<int> v[MAX_N];  //제거할 간선
bool check[MAX_N][MAX_N];  //최단거리에 포함된 간선

void input()
{
    //배열 초기화하기
    for(int i=0; i<MAX_N; i++) {
        Vertex[i].clear();
        v[i].clear();
    }
    memset(check, false, sizeof check);
    
    cin >> N >> M; cin >> S >> D;
    for(int i=1; i<=M; i++) {
        int u, v, p;  //u에서 v로 가는 도로의 길이가 p
        
        cin >> u >> v >> p;
        Vertex[u].push_back({v, p});
    }
}

int Dijkstra()
{
    fill(Dist, Dist+MAX_N, INF);
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, S});  //처음 위치
    Dist[S]=0;
    
    while(!pq.empty()) {
        int Cost = pq.top().Fi, Cur = pq.top().Se;  //우선순위 큐에서 제일 낮은 가중치를 가진 곳에서 빼오기
        pq.pop();
        
        for(auto x : Vertex[Cur]) {
            int Next = x.Fi;  //다음 노드
            int NCost = x.Se;  //간선의 가중치
            
            if(check[Cur][Next]) continue;  //최단 경로이면 pass
            
            if(Dist[Next] == Dist[Cur] + NCost)
                v[Next].push_back(Cur);
            
            if(Dist[Next] > NCost + Dist[Cur]) {  //이 길의 가중치 합이 작다면 갱신하기
                Dist[Next] = NCost + Dist[Cur];
                pq.push({Dist[Next], Next});
                v[Next].clear(); v[Next].push_back(Cur);
            }
        }
    }
    
    return Dist[D] == INF ? -1:Dist[D];
}

void erase(int Cur)
{
    for(auto x : v[Cur]) {
        if(!check[x][Cur]) {
            check[x][Cur] = true;
            erase(x);
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    while(1) {  //테스트 케이스가 여러 개
        input();
        if(!N && !M) break;  //테스트 케이스의 마지막은 0, 0
        
        Dijkstra();
        erase(D);
        cout << Dijkstra() << '\n';  //다시 다익스트라
    }
    
    return 0;
}

 

<테스트케이스 모음>

https://www.acmicpc.net/board/view/102349

글 읽기 - 테스트케이스 모음

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.