œœœGraph G8œœœ #define N 12 int edge[N][N] = { /* 0 1 2 3 4 5 6 7 8 9 10 11*/ /* 0 */ { 0, 4,NC,NC, 3,NC,NC,NC,NC,NC,NC,NC}, /* 1 */ { 4, 0, 1,NC,NC,NC, 2,NC,NC,NC,NC,NC}, /* 2 */ {NC, 1, 0, 1,NC,NC,NC, 2,NC,NC,NC,NC}, /* 3 */ {NC,NC, 1, 0,NC,NC,NC,NC,NC,NC,NC,NC}, /* 4 */ { 3,NC,NC,NC, 0, 1,NC,NC, 1,NC,NC,NC}, /* 5 */ {NC,NC,NC,NC, 1, 0, 2,NC,NC, 2, 3,NC}, /* 6 */ {NC, 2,NC,NC,NC, 2, 0,NC,NC,NC, 3,NC}, /* 7 */ {NC,NC, 2,NC,NC,NC,NC, 0,NC,NC,NC,NC}, /* 8 */ {NC,NC,NC,NC, 1,NC,NC,NC, 0,NC,NC,NC}, /* 9 */ {NC,NC,NC,NC,NC, 2,NC,NC,NC, 0,NC,NC}, /*10 */ {NC,NC,NC,NC,NC, 3, 3,NC,NC,NC, 0, 1}, /*11 */ {NC,NC,NC,NC,NC,NC,NC,NC,NC,NC, 1, 0} }; œœœResult Sampleœœœ COST * 4 5 6 3 4 6 7 4 6 7 8 4 * 1 2 5 4 2 3 6 6 5 6 5 1 * 1 6 5 3 2 7 7 6 7 6 2 1 * 7 6 4 3 8 8 7 8 3 5 6 7 * 1 3 8 1 3 4 5 4 4 5 6 1 * 2 7 2 2 3 4 6 2 3 4 3 2 * 5 4 4 3 4 7 3 2 3 8 7 5 * 9 9 8 9 4 6 7 8 1 2 4 9 * 4 5 6 6 6 7 8 3 2 4 9 4 * 5 6 7 5 6 7 4 3 3 8 5 5 * 1 8 6 7 8 5 4 4 9 6 6 1 * VIA 0 0 1 2 0 4 1 2 4 5 5 10 1 1 1 2 6 6 1 2 6 6 6 10 1 2 2 2 6 6 1 2 6 6 6 10 2 2 3 3 6 6 2 2 6 6 6 10 4 6 6 6 4 4 5 6 4 5 5 10 4 6 6 6 5 5 5 6 4 5 5 10 1 6 1 2 5 6 6 2 5 5 6 10 2 2 7 2 6 6 2 7 6 6 6 10 4 6 6 6 8 4 5 6 8 5 5 10 5 6 6 6 5 9 5 6 5 9 5 10 5 6 6 6 5 10 10 6 5 5 10 10 10 10 10 10 10 10 10 10 10 10 11 11 PATH 0 => 0 [**] 0 => 1 [ 4] 0 1 0 => 2 [ 5] 0 1 2 0 => 3 [ 6] 0 1 2 3 0 => 4 [ 3] 0 4 0 => 5 [ 4] 0 4 5 0 => 6 [ 6] 0 1 6 0 => 7 [ 7] 0 1 2 7 0 => 8 [ 4] 0 4 8 0 => 9 [ 6] 0 4 5 9 0 => 10 [ 7] 0 4 5 10 0 => 11 [ 8] 0 4 5 10 11 1 => 0 [ 4] 1 0 1 => 1 [**] 1 => 2 [ 1] 1 2 1 => 3 [ 2] 1 2 3 1 => 4 [ 5] 1 6 5 4 1 => 5 [ 4] 1 6 5 1 => 6 [ 2] 1 6 1 => 7 [ 3] 1 2 7 1 => 8 [ 6] 1 6 5 4 8 1 => 9 [ 6] 1 6 5 9 1 => 10 [ 5] 1 6 10 1 => 11 [ 6] 1 6 10 11 2 => 0 [ 5] 2 1 0 2 => 1 [ 1] 2 1 2 => 2 [**] 2 => 3 [ 1] 2 3 2 => 4 [ 6] 2 1 6 5 4 2 => 5 [ 5] 2 1 6 5 2 => 6 [ 3] 2 1 6 2 => 7 [ 2] 2 7 2 => 8 [ 7] 2 1 6 5 4 8 2 => 9 [ 7] 2 1 6 5 9 2 => 10 [ 6] 2 1 6 10 2 => 11 [ 7] 2 1 6 10 11 3 => 0 [ 6] 3 2 1 0 3 => 1 [ 2] 3 2 1 3 => 2 [ 1] 3 2 3 => 3 [**] 3 => 4 [ 7] 3 2 1 6 5 4 3 => 5 [ 6] 3 2 1 6 5 3 => 6 [ 4] 3 2 1 6 3 => 7 [ 3] 3 2 7 3 => 8 [ 8] 3 2 1 6 5 4 8 3 => 9 [ 8] 3 2 1 6 5 9 3 => 10 [ 7] 3 2 1 6 10 3 => 11 [ 8] 3 2 1 6 10 11 4 => 0 [ 3] 4 0 4 => 1 [ 5] 4 5 6 1 4 => 2 [ 6] 4 5 6 1 2 4 => 3 [ 7] 4 5 6 1 2 3 4 => 4 [**] 4 => 5 [ 1] 4 5 4 => 6 [ 3] 4 5 6 4 => 7 [ 8] 4 5 6 1 2 7 4 => 8 [ 1] 4 8 4 => 9 [ 3] 4 5 9 4 => 10 [ 4] 4 5 10 4 => 11 [ 5] 4 5 10 11 5 => 0 [ 4] 5 4 0 5 => 1 [ 4] 5 6 1 5 => 2 [ 5] 5 6 1 2 5 => 3 [ 6] 5 6 1 2 3 5 => 4 [ 1] 5 4 5 => 5 [**] 5 => 6 [ 2] 5 6 5 => 7 [ 7] 5 6 1 2 7 5 => 8 [ 2] 5 4 8 5 => 9 [ 2] 5 9 5 => 10 [ 3] 5 10 5 => 11 [ 4] 5 10 11 6 => 0 [ 6] 6 1 0 6 => 1 [ 2] 6 1 6 => 2 [ 3] 6 1 2 6 => 3 [ 4] 6 1 2 3 6 => 4 [ 3] 6 5 4 6 => 5 [ 2] 6 5 6 => 6 [**] 6 => 7 [ 5] 6 1 2 7 6 => 8 [ 4] 6 5 4 8 6 => 9 [ 4] 6 5 9 6 => 10 [ 3] 6 10 6 => 11 [ 4] 6 10 11 7 => 0 [ 7] 7 2 1 0 7 => 1 [ 3] 7 2 1 7 => 2 [ 2] 7 2 7 => 3 [ 3] 7 2 3 7 => 4 [ 8] 7 2 1 6 5 4 7 => 5 [ 7] 7 2 1 6 5 7 => 6 [ 5] 7 2 1 6 7 => 7 [**] 7 => 8 [ 9] 7 2 1 6 5 4 8 7 => 9 [ 9] 7 2 1 6 5 9 7 => 10 [ 8] 7 2 1 6 10 7 => 11 [ 9] 7 2 1 6 10 11 8 => 0 [ 4] 8 4 0 8 => 1 [ 6] 8 4 5 6 1 8 => 2 [ 7] 8 4 5 6 1 2 8 => 3 [ 8] 8 4 5 6 1 2 3 8 => 4 [ 1] 8 4 8 => 5 [ 2] 8 4 5 8 => 6 [ 4] 8 4 5 6 8 => 7 [ 9] 8 4 5 6 1 2 7 8 => 8 [**] 8 => 9 [ 4] 8 4 5 9 8 => 10 [ 5] 8 4 5 10 8 => 11 [ 6] 8 4 5 10 11 9 => 0 [ 6] 9 5 4 0 9 => 1 [ 6] 9 5 6 1 9 => 2 [ 7] 9 5 6 1 2 9 => 3 [ 8] 9 5 6 1 2 3 9 => 4 [ 3] 9 5 4 9 => 5 [ 2] 9 5 9 => 6 [ 4] 9 5 6 9 => 7 [ 9] 9 5 6 1 2 7 9 => 8 [ 4] 9 5 4 8 9 => 9 [**] 9 => 10 [ 5] 9 5 10 9 => 11 [ 6] 9 5 10 11 10 => 0 [ 7] 10 5 4 0 10 => 1 [ 5] 10 6 1 10 => 2 [ 6] 10 6 1 2 10 => 3 [ 7] 10 6 1 2 3 10 => 4 [ 4] 10 5 4 10 => 5 [ 3] 10 5 10 => 6 [ 3] 10 6 10 => 7 [ 8] 10 6 1 2 7 10 => 8 [ 5] 10 5 4 8 10 => 9 [ 5] 10 5 9 10 => 10 [**] 10 => 11 [ 1] 10 11 11 => 0 [ 8] 11 10 5 4 0 11 => 1 [ 6] 11 10 6 1 11 => 2 [ 7] 11 10 6 1 2 11 => 3 [ 8] 11 10 6 1 2 3 11 => 4 [ 5] 11 10 5 4 11 => 5 [ 4] 11 10 5 11 => 6 [ 4] 11 10 6 11 => 7 [ 9] 11 10 6 1 2 7 11 => 8 [ 6] 11 10 5 4 8 11 => 9 [ 6] 11 10 5 9 11 => 10 [ 1] 11 10 11 => 11 [**]