최적 경로 선택

다중 출발점 및 도착점 최단 경로 문제는 가상 출발점을 설정하여 해결할 수 있습니다. 이 문제에서는 다음과 같은 알고리즘이 사용될 수 있습니다:

• 위상 정렬: SPFA 알고리즘은 음의 가중치가 있을 때 사용 가능합니다. 먼저 최단 경로를 구한 후, 필요한 작업을 수행합니다.
• BFS: 가중치가 없는 그래프에서 효과적입니다.
• Dijkstra 알고리즘: 양의 가중치가 있는 그래프에 적합합니다.

최단 경로 개수 세기

최단 경로를 세기 위한 두 가지 중요한 원리:

1. 최단 경로 조건: 값이 0인 루프(사이클)가 존재할 수 없습니다.
2. 그래프를 최단 경로 트리로 추상화할 수 있습니다. 이를 통해 각 업데이트 지점의 부모 노드가 이미 완전히 업데이트되었음을 보장할 수 있습니다.

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;
const int MAXN = 1e5+10, MAXM = 4e5+5, MOD = 100003;
int head[MAXN], nextEdge[MAXM], destination[MAXM], edgeIdx;
void addEdge(int from, int to) {
    destination[edgeIdx] = to;
    nextEdge[edgeIdx] = head[from];
    head[from] = edgeIdx++;
}
int distance[MAXN], countPath[MAXN];
void bfs() {
    queue<int>q;
    q.push(1);
    memset(distance, 0x3f, sizeof distance);
    distance[1] = 0;
    countPath[1] = 1;
    
    while(!q.empty()) {
        int current = q.front();
        q.pop();
        for (int i = head[current]; ~i ; i = nextEdge[i]) {
            int neighbor = destination[i];
            
            if(distance[neighbor] > distance[current] + 1) {
                distance[neighbor] = distance[current] + 1;
                countPath[neighbor] = countPath[current];
                q.push(neighbor);
            } else if(distance[neighbor] == distance[current] + 1) {
                countPath[neighbor] = (countPath[current] + countPath[neighbor]) % MOD;
            } 
        }
    }
}
int main() {
    int nodeCount, edgeCount;
    cin >> nodeCount >> edgeCount;
    memset(head, -1, sizeof head);
    while(edgeCount--) {
        int from, to;
        cin >> from >> to;
        addEdge(from, to);
        addEdge(to, from);
    }
    bfs();
    for (int i = 1; i <= nodeCount; i++ ) {
        cout << countPath[i] << endl;
    }
    return 0;
}

관광 경로 문제

이 문제에서는 두 가지 상태를 고려해야 합니다:

1. dist[i][0,1]: 초기 도시 S에서 도시 i까지의 최단 거리와 차단 거리
2. cnt[i][0,1]: 초기 도시 S에서 도시 i까지의 최단 경로와 차단 경로의 수

초기 상태에서는 dist[S][0]가 0이고, cnt[S][0]가 1로 설정됩니다 (나머지는 양의 무한대로 초기화).

Dijkstra 알고리즘을 사용할 때 도시 t에서 도시 j로 이동하는 네 가지 경우를 고려해야 합니다:

• dist[j][0] > dist[v][type] + w[i]: 새로운 최단 경로 발견. 기존 최단 경로는 차단 경로로 변경됩니다.
• dist[j][0] == dist[v][type] + w[i]: 동일한 길이의 새로운 최단 경로 발견.
• dist[j][1] > dist[v][type] + w[i]: 새로운 차단 경로 발견.
• dist[j][1] == dist[v][type] + w[i]: 동일한 길이의 새로운 차단 경로 발견.

최종적으로 목적지 도시 F의 차단 경로가 최단 경로보다 정확히 1만큼 길다면, 해당 경로의 수를 결과에 더합니다.

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
const int N = 1010, M = 10010;
int head[N], edge[M], nextEdge[M], weight[M], edgeIdx;
// 상태 0: 최단 경로, 상태 1: 차단 경로
int pathCount[N][2];  // pathCount[i][0]: 노드 i에 도달하는 최단 경로 수
int distance[N][2]; // distance[i][0]: 노드 i까지의 최단 거리
bool visited[N][2];  // 방문 여부
int nodeCount, edgeCount, start, end;  // 시작점과 종점

struct Node{   // 최소 힙, greater 연산자 오버로딩
    int id, type, dist;   // 노드 번호, 상태, 시작점까지의 거리
    bool operator> (const Node& a) const{  // 오름차순 정렬
        return dist > a.dist;
    }
};

void addEdge(int from, int to, int cost){
    weight[edgeIdx] = cost;
    edge[edgeIdx] = to;
    nextEdge[edgeIdx] = head[from];
    head[from] = edgeIdx++;
}

int dijkstra(){

    memset(visited, 0, sizeof visited);
    memset(distance, 0x3f, sizeof distance);
    memset(pathCount, 0, sizeof pathCount);

    priority_queue<Node,vector<Node>,greater<Node>> heap;
    distance[start][0] = 0;
    pathCount[start][0] = 1;
    heap.push({start,0,0});//(노드, 상태, 거리)

    while(!heap.empty()){

        Node current = heap.top();
        heap.pop();

        int vertex = current.id , state = current.type , dist = current.distance; 

        if(visited[vertex][state]) continue;
        visited[vertex][state] = true;


        for(int i = head[vertex];i != -1;i = nextEdge[i]){
            int neighbor = edge[i];

            // 최단 경로 경우 (초과, 동일)
            if(distance[neighbor][0] > distance[vertex][state] + weight[i]){
                // 기존 최단 경로를 차단 경로로 변경
                distance[neighbor][1] = distance[neighbor][0]; 
                pathCount[neighbor][1] = pathCount[neighbor][0];
                heap.push({neighbor, 1, distance[neighbor][1]});  // 거리 변경 시 큐에 추가

                distance[neighbor][0] = distance[vertex][state] + weight[i];  
                pathCount[neighbor][0] = pathCount[vertex][state];  
                heap.push({neighbor,0,distance[neighbor][0]}); // 거리 변경 시 큐에 추가

            }else if(distance[neighbor][0] == distance[vertex][state] + weight[i]){  

                pathCount[neighbor][0] += pathCount[vertex][state]; // 새로운 최단 경로 추가

            // 차단 경로 경우
            }else if(distance[neighbor][1] > distance[vertex][state] + weight[i]){

                distance[neighbor][1] = distance[vertex][state] + weight[i];
                pathCount[neighbor][1] = pathCount[vertex][state];
                 heap.push({neighbor, 1, distance[neighbor][1]});

            }else if(distance[neighbor][1] == distance[vertex][state] + weight[i]){
                pathCount[neighbor][1] += pathCount[vertex][state];  // 새로운 차단 경로 추가
            } 
        }
    }
    int result = pathCount[end][0];
    // 최단 경로와 차단 경로의 차이가 1인 경우 결과에 추가
    if (distance[end][0] + 1 == distance[end][1]) result += pathCount[end][1];  
    return result;
}

int main(){
    int testCases;
    cin >> testCases;
    while(testCases--){
        memset(head,-1,sizeof head);
        cin >> nodeCount >> edgeCount;
        for(int i = 0;i < edgeCount;++i){
            int from, to, cost;
            scanf("%d%d%d",&from,&to,&cost);
            addEdge(from,to,cost);
        }
        scanf("%d%d",&start,&end);
        cout << dijkstra() << endl;
    }
    return 0;
}