지하철-SPJ(BFS)

문제 설명

---

지방에서 서울에 관광 온 성수는 지하철 노선을 보고 깜짝 놀랐다. 노선이 엄청나게 복잡하기 때문이었다. 각 노선들이 서로 얽혀있어서 잘못하면 10분도 안 걸리는 거리를 1시간 동안 갈 수도 있는 상황이었다. 어쩔 수 없이 성수는 현재 숙소에서 관광할 목적지까지 가장 짧은 시간에 도착할 수 있는 경로와 시간을 표로 만들려고 한다.

단, 각 지하철역에서 관광지가 있고, 지하철을 갈아타는데 소요되는 시간은 없다고 가정한다.

입력 설명

---

첫 줄에 N(3<= N <= 100), M(1<= M <= N)을 입력 받는다. N은 지하철역의 수, M은 원하는 목적역의 번호를 입력 받는다.

둘째 줄부터 N개의 줄이 나오고, 각 줄에는 N개의 수 S가 입력된다.

i번째 줄에서 j번째 수 Sij는 i번 역에서 j번 역까지 가는데 걸리는 시간이다. 1번 역이 숙소가 있는 역이고, Sij에서 i=j 일 때는 항상 0이다. (0<= S <=100)

출력 설명

---

목적 역까지 가는데 걸리는 최소 시간과 최소시간으로 가는 최단 경로를 출력한다.

입력 예시

---

5 5
0 2 2 5 9
2 0 3 4 8
2 3 0 7 6
5 4 7 0 5
9 5 6 5 0

출력 예시

---

8
1 3 5

#include <stdio.h>
#define MAXN (100)
int N, M;//지하철역수, 목적역
int S[MAXN+2][MAXN+2];//[s][e]=시간
 
#define INF (1<<30)
int visited[MAXN+2];
int path[MAXN+2];
 
int que[MAXN * 100];
int wp, rp;
void push(int n){
    que[wp++] = n;
}
void pop(void){
    rp++;
}
int front(void){
    return que[rp];
}
int empty(void){
    return wp==rp;
}
 
int BFS(){
    for (int i=1; i<=N; i++){
        visited[i] = INF;
        path[i] = 0;
    }
    wp = rp = 0;
    push(1);
    visited[1]=0;
    path[1]=0;
    while (!empty()){
        int cur = front(); pop();
        for (int e=2; e<=N; e++){
            int ntime = visited[cur] + S[cur][e];
            if (visited[e] <= ntime) continue;
            push(e);
            visited[e] = ntime;
            path[e]=cur;
        }
    }
    return visited[M];
}
 
void PRT(int m){
    if (m == 0) return;
    PRT(path[m]);
    printf("%d ", m);
}
void OutputData(int ans){
    printf("%d\n", ans);
    PRT(M);
    printf("\n");
}
 
void InputData(void){
    scanf("%d %d", &N, &M);
    for (int s=1; s<=N; s++){
        for (int e=1; e<=N; e++){
            scanf("%d", &S[s][e]);
        }
    }
}
 
int main(void){
    InputData();
    int ans = BFS();
    OutputData(ans);
    return 0;
}