#include <stdio.h>
 
#define INF 99999
#define N 6
 
int graph[N][N] = {
    {0, 2, INF, 8, INF, INF},
    {2, 0, INF, 5, 6, INF},
    {INF, INF, 0, INF, 9, 3},
    {8, 5, INF, 0, INF, 2},
    {INF, 6, 9, INF, 0, 1},
    {INF, INF, 3, 2, 1, 0}
};
 
void floydWarshall(int dist[N][N], int pred[N][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            dist[i][j] = graph[i][j];
            if (graph[i][j] != INF && i != j)
                pred[i][j] = i;
            else
                pred[i][j] = -1;
        }
    }
 
    for (int k = 0; k < N; k++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    pred[i][j] = pred[k][j];  // แก้ไขตรงนี้เพื่อให้ Predecessor Matrix อัปเดตถูกต้อง
                }
            }
        }
    }
}
 
void printPath(int pred[N][N], int start, int end) {
    if (pred[start][end] == -1) {
        printf("ไม่มีเส้นทางจาก %c ไป %c\n", start + 'A', end + 'A');
        return;
    }
 
    int path[N], count = 0;
    int current = end;
 
    while (current != start) {
        path[count++] = current;
        current = pred[start][current];
    }
    path[count++] = start;
 
    printf("เส้นทางที่สั้นที่สุดจาก %c ไป %c: ", start + 'A', end + 'A');
    for (int i = count - 1; i >= 0; i--) {
        printf("%c", path[i] + 'A');
        if (i > 0) printf(" → ");
    }
    printf("\n");
}
 
int main() {
    int dist[N][N], pred[N][N];
 
    floydWarshall(dist, pred);
 
    printf("ระยะทางที่สั้นที่สุดจาก A ไป C: %d\n", dist[0][2]);
    printPath(pred, 0, 2);
 
    return 0;
}

I2luY2x1ZGUgPHN0ZGlvLmg+CgojZGVmaW5lIElORiA5OTk5OQojZGVmaW5lIE4gNgoKaW50IGdyYXBoW05dW05dID0gewogICAgezAsIDIsIElORiwgOCwgSU5GLCBJTkZ9LAogICAgezIsIDAsIElORiwgNSwgNiwgSU5GfSwKICAgIHtJTkYsIElORiwgMCwgSU5GLCA5LCAzfSwKICAgIHs4LCA1LCBJTkYsIDAsIElORiwgMn0sCiAgICB7SU5GLCA2LCA5LCBJTkYsIDAsIDF9LAogICAge0lORiwgSU5GLCAzLCAyLCAxLCAwfQp9OwoKdm9pZCBmbG95ZFdhcnNoYWxsKGludCBkaXN0W05dW05dLCBpbnQgcHJlZFtOXVtOXSkgewogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBOOyBpKyspIHsKICAgICAgICBmb3IgKGludCBqID0gMDsgaiA8IE47IGorKykgewogICAgICAgICAgICBkaXN0W2ldW2pdID0gZ3JhcGhbaV1bal07CiAgICAgICAgICAgIGlmIChncmFwaFtpXVtqXSAhPSBJTkYgJiYgaSAhPSBqKQogICAgICAgICAgICAgICAgcHJlZFtpXVtqXSA9IGk7CiAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgIHByZWRbaV1bal0gPSAtMTsKICAgICAgICB9CiAgICB9CgogICAgZm9yIChpbnQgayA9IDA7IGsgPCBOOyBrKyspIHsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IE47IGkrKykgewogICAgICAgICAgICBmb3IgKGludCBqID0gMDsgaiA8IE47IGorKykgewogICAgICAgICAgICAgICAgaWYgKGRpc3RbaV1ba10gIT0gSU5GICYmIGRpc3Rba11bal0gIT0gSU5GICYmIGRpc3RbaV1ba10gKyBkaXN0W2tdW2pdIDwgZGlzdFtpXVtqXSkgewogICAgICAgICAgICAgICAgICAgIGRpc3RbaV1bal0gPSBkaXN0W2ldW2tdICsgZGlzdFtrXVtqXTsKICAgICAgICAgICAgICAgICAgICBwcmVkW2ldW2pdID0gcHJlZFtrXVtqXTsgIC8vIOC5geC4geC5ieC5hOC4guC4leC4o+C4h+C4meC4teC5ieC5gOC4nuC4t+C5iOC4reC5g+C4q+C5iSBQcmVkZWNlc3NvciBNYXRyaXgg4Lit4Lix4Lib4LmA4LiU4LiV4LiW4Li54LiB4LiV4LmJ4Lit4LiHCiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9Cn0KCnZvaWQgcHJpbnRQYXRoKGludCBwcmVkW05dW05dLCBpbnQgc3RhcnQsIGludCBlbmQpIHsKICAgIGlmIChwcmVkW3N0YXJ0XVtlbmRdID09IC0xKSB7CiAgICAgICAgcHJpbnRmKCLguYTguKHguYjguKHguLXguYDguKrguYnguJnguJfguLLguIfguIjguLLguIEgJWMg4LmE4LibICVjXG4iLCBzdGFydCArICdBJywgZW5kICsgJ0EnKTsKICAgICAgICByZXR1cm47CiAgICB9CgogICAgaW50IHBhdGhbTl0sIGNvdW50ID0gMDsKICAgIGludCBjdXJyZW50ID0gZW5kOwoKICAgIHdoaWxlIChjdXJyZW50ICE9IHN0YXJ0KSB7CiAgICAgICAgcGF0aFtjb3VudCsrXSA9IGN1cnJlbnQ7CiAgICAgICAgY3VycmVudCA9IHByZWRbc3RhcnRdW2N1cnJlbnRdOwogICAgfQogICAgcGF0aFtjb3VudCsrXSA9IHN0YXJ0OwoKICAgIHByaW50Zigi4LmA4Liq4LmJ4LiZ4LiX4Liy4LiH4LiX4Li14LmI4Liq4Lix4LmJ4LiZ4LiX4Li14LmI4Liq4Li44LiU4LiI4Liy4LiBICVjIOC5hOC4myAlYzogIiwgc3RhcnQgKyAnQScsIGVuZCArICdBJyk7CiAgICBmb3IgKGludCBpID0gY291bnQgLSAxOyBpID49IDA7IGktLSkgewogICAgICAgIHByaW50ZigiJWMiLCBwYXRoW2ldICsgJ0EnKTsKICAgICAgICBpZiAoaSA+IDApIHByaW50ZigiIOKGkiAiKTsKICAgIH0KICAgIHByaW50ZigiXG4iKTsKfQoKaW50IG1haW4oKSB7CiAgICBpbnQgZGlzdFtOXVtOXSwgcHJlZFtOXVtOXTsKCiAgICBmbG95ZFdhcnNoYWxsKGRpc3QsIHByZWQpOwoKICAgIHByaW50Zigi4Lij4Liw4Lii4Liw4LiX4Liy4LiH4LiX4Li14LmI4Liq4Lix4LmJ4LiZ4LiX4Li14LmI4Liq4Li44LiU4LiI4Liy4LiBIEEg4LmE4LibIEM6ICVkXG4iLCBkaXN0WzBdWzJdKTsKICAgIHByaW50UGF0aChwcmVkLCAwLCAyKTsKCiAgICByZXR1cm4gMDsKfQ==