#include <stdio.h>
#include <stdlib.h>
#define N 6
#define INF 9999
int flag[N + 1];
int dist[N + 1];
int index[N + 1];
int min, position;
int data[N + 1][N + 1] =
{{0, 0, 0, 0, 0, 0, 0},
{0, 0, 2,INF, 3,INF,INF},
{0,INF, 0, 4 , 1, 7,INF},
{0,INF,INF, 0, 4, 1, 3},
{0,INF, 2, 2, 0, 1,INF},
{0,INF,INF, 1,INF, 0, 6},
{0,INF, 3,INF, 8,INF, 0}};
int main()
{
for (int i = 1; i <= N; i++) {
flag[i] = 0;
dist[i] = INF;
}
dist[1] = 0;
for (int i = 1; i <= N; i++) {
min = INF;
for (int j = 1; j <= N; j++) {
if (min > dist[j] && flag[j] == 0) {
min = dist[j] + data[j][0];
position = j;
}
}
flag[position] = 1;
for (int j = 1; j <= N; j++) {
if (dist[j] > dist[position] + data[position][j] && data[position][j] != INF) {
dist[j] = dist[position] + data[position][j];
index[j] = position;
}
}
}
for (int i = 1; i <= N; i++) {
printf("1 ~ %d : %d Path: %d", i
, dist
[i
], i
); position = i;
do {
printf(" <- %d", index
[position
]); position = index[position];
} while (index[position]);
}
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KCiNkZWZpbmUgTiA2CiNkZWZpbmUgSU5GIDk5OTkKCmludCBmbGFnW04gKyAxXTsKaW50IGRpc3RbTiArIDFdOwppbnQgaW5kZXhbTiArIDFdOwoKaW50IG1pbiwgcG9zaXRpb247CgppbnQgZGF0YVtOICsgMV1bTiArIDFdID0gCnt7MCwgMCwgMCwgMCwgMCwgMCwgMH0sCnswLCAwLCAyLElORiwgMyxJTkYsSU5GfSwKezAsSU5GLCAwLCA0ICwgMSwgNyxJTkZ9LAp7MCxJTkYsSU5GLCAwLCA0LCAxLCAzfSwKezAsSU5GLCAyLCAyLCAwLCAxLElORn0sCnswLElORixJTkYsIDEsSU5GLCAwLCA2fSwKezAsSU5GLCAzLElORiwgOCxJTkYsIDB9fTsKCmludCBtYWluKCkKewogICBmb3IgKGludCBpID0gMTsgaSA8PSBOOyBpKyspIHsKICAgICAgZmxhZ1tpXSA9IDA7CiAgICAgIGRpc3RbaV0gPSBJTkY7CiAgIH0KCiAgIGRpc3RbMV0gPSAwOwogICAKICAgZm9yIChpbnQgaSA9IDE7IGkgPD0gTjsgaSsrKSB7CiAgICAgIG1pbiA9IElORjsKICAgICAgZm9yIChpbnQgaiA9IDE7IGogPD0gTjsgaisrKSB7CiAgICAgICAgIGlmIChtaW4gPiBkaXN0W2pdICYmIGZsYWdbal0gPT0gMCkgewogICAgICAgICAgICBtaW4gPSBkaXN0W2pdICsgZGF0YVtqXVswXTsKICAgICAgICAgICAgcG9zaXRpb24gPSBqOwogICAgICAgICB9CiAgICAgIH0KICAgICAgZmxhZ1twb3NpdGlvbl0gPSAxOwogICAgICBmb3IgKGludCBqID0gMTsgaiA8PSBOOyBqKyspIHsKICAgICAgICAgaWYgKGRpc3Rbal0gPiBkaXN0W3Bvc2l0aW9uXSArIGRhdGFbcG9zaXRpb25dW2pdICYmIGRhdGFbcG9zaXRpb25dW2pdICE9IElORikgewogICAgICAgICAgICBkaXN0W2pdID0gZGlzdFtwb3NpdGlvbl0gKyBkYXRhW3Bvc2l0aW9uXVtqXTsKICAgICAgICAgICAgaW5kZXhbal0gPSBwb3NpdGlvbjsKICAgICAgICAgfQogICAgICB9CiAgIH0KICAgZm9yIChpbnQgaSA9IDE7IGkgPD0gTjsgaSsrKSB7CiAgICAgIHByaW50ZigiMSB+ICVkIDogJWQgUGF0aDogJWQiLCBpLCBkaXN0W2ldLCBpKTsKICAgICAgcG9zaXRpb24gPSBpOwogICAgICBkbyB7CiAgICAgICAgIHByaW50ZigiIDwtICVkIiwgaW5kZXhbcG9zaXRpb25dKTsKICAgICAgICAgcG9zaXRpb24gPSBpbmRleFtwb3NpdGlvbl07CiAgICAgIH0gd2hpbGUgKGluZGV4W3Bvc2l0aW9uXSk7CiAgICAgIHB1dHMoIiIpOwogICB9Cn0=