Dijkstra 응용 차 단락

우 리 는 모두 Dijkstra 알고리즘 이 단원 의 가장 짧 은 길 을 구 하 는 알고리즘 이라는 것 을 안다.그렇다면 지금 우리 의 문 제 는 최 단 로 가 아니 라 차 단 로 (두 번 째 짧 은 경로) 다.저희 가 지금 DIjkstra 알고리즘 을 사용 할 수 있 을까요?당연 하지, 너 는 이 블 로그 의 이름 을 보면 알 수 있어.사실 처음에 저도 Dijkstra 로 단락 문 제 를 풀 줄 은 몰 랐 습 니 다. '도전 프로 그래 밍 경연 대회' 를 보면 서 이런 해법 을 보고 너무 신기해 서 여러분 과 공유 하 러 왔 습 니 다.
        그럼 이제 Dijkstra 가 최 단 로 문 제 를 어떻게 풀 었 는 지 기억 해 보 자.Dijkstra 의 사상 은 최 단 로 의 정점 을 확정 하여 정점 이 확정 되 지 않 은 최 단 로 를 계산 하 는 것 입 니 다. 이 말 은 무슨 뜻 입 니까?예 를 들 어 무 방향 그림 에서 s 는 원점 이 고 v1 은 최 단 로 의 정점 이 며 v2, v3 는 아직 확정 되 지 않 은 정점 이다.그러면 우 리 는 v1 의 최 단 거리 에 v1 - > v2 또는 v3 의 거 리 를 더 해서 v2, v3 에서 원점 s 까지 의 거 리 를 업데이트 합 니 다.분명히 이렇게 계속 업데이트 되면 최종 s 에서 v2, v3 까지 의 거 리 는 가장 짧 은 거리 입 니 다.
        dist [v] 가 s - > v 의 최 단 거 리 를 나타 내 면 dist 2 [v] 는 s - > v 의 차 단 거 리 를 나타 내 고 d 는 s - > v 의 제 k 단거리 (k > 1) 를 나타 낸다.그러면 반드시 이러한 관 계 를 만족 시 킬 것 입 니 다. dist [v] < dist 2 [v] < = k.이 등식 을 보 았 을 때 우 리 는 dist 2 [v] > d2 > dist [v] 를 발견 할 수 있다. 분명히 이때 우 리 는 dist 2 [v] 를 d2 로 업데이트 해 야 한다.그러면 우 리 는 dist [v] < dist 2 [v] < = k 라 는 식 의 dist 2 [v] 만 만족 하지 않 는 다 면 우 리 는 그 를 업데이트 할 것 이다.그래서 식 이 이 식 을 만족 시 킬 때 까지 계속 업데이트 되면 dist 2 [v] 는 원점 s - > v 의 차 단락 입 니 다.여기 서 우 리 는 이미 단락 을 푸 는 방법 을 내 놓 았 다.
        옛 규칙, 물 문제 에 와 서 연습 하 는 POJ 3255 Roadblocks.문제 풀이 코드 는 다음 과 같 습 니 다.

#include 
#include 
#include 
#include 
#define MAXN (5000 + 10)
#define INF (5000*5000*2)
using namespace std;

struct edge{
    int to, cost;
    edge(int tv = 0, int tc = 0):
        to(tv), cost(tc){}
};
typedef pair P;
int N, R;
vector graph[MAXN];
int dist[MAXN];     //    
int dist2[MAXN];    //    

void solve(){
    fill(dist, dist+N, INF);
    fill(dist2, dist2+N, INF);
    //         
    //  pair   edge   
    //               
    //pair  first         
    priority_queue
, greater
 > Q;
    //       
    dist[0] = 0;
    Q.push(P(0, 0));
    //           
    while(!Q.empty()){
        P p = Q.top(); Q.pop();
        //first s->to   ，second edge    to
        int v = p.second, d = p.first;
        //                  ，    
        if(dist2[v] < d) continue;
        for(unsigned i = 0; i < graph[v].size(); i++){
            edge &e = graph[v][i];
            int d2 = d + e.cost;
            if(dist[e.to] > d2){
                swap(dist[e.to], d2);
                Q.push(P(dist[e.to], e.to));
            }
            if(dist2[e.to] > d2 && dist[v] < d2){
                dist2[e.to] = d2;
                Q.push(P(dist2[e.to], e.to));
            }
        }
    }
    printf("%d
", dist2[N-1]);
}

int main(){
    int A, B, D;
    scanf("%d%d", &N, &R);
    for(int i = 0; i < R; i++){
        scanf("%d%d%d", &A, &B, &D);
        graph[A-1].push_back(edge(B-1, D));
        graph[B-1].push_back(edge(A-1, D));
    }
    solve();
    return 0;
}