#include <iostream>
using namespace std;
const int N = 7;
const int INF = 1e3;
int g[N][N] = {
{ INF, 2, INF, 2,4, 3, INF },
{ 2, INF, 2, INF, INF, 1, INF },
{ INF, 2, INF, 2, INF, INF, 2 },
{ 2, INF, 2, INF, 3, INF, INF },
{ 4, INF, INF, 3, INF, 1, INF },
{ 3, 1, INF, INF, 1, INF, 2 },
{ INF, INF, 2,INF, INF, 2, INF } };
int dis[N], vis[N];
void dijkstra(int s) {
vis[s] = 1;
for (int i = 0; i < N; i++) {
dis[i] = g[s][i];
}
for (int i = 0; i < N; i++) {
int pos = 0, Min = INF;
for (int j = 0; j < N; j++) {
if (!vis[j] && dis[j] < Min) {
pos = j;
Min = dis[pos];
}
}
if (pos) {
vis[pos] = 1;
for (int j = 0; j < N; j++) {
if (j != s && dis[pos] + g[pos][j] < dis[j]) {
dis[j] = dis[pos] + g[pos][j];
}
}
}
}
}
int main() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cout << g[i][j] << " ";
}
cout << endl;
}
// 1000 2 1000 2 4 3 1000
// 2 1000 2 1000 1000 1 1000
// 1000 2 1000 2 1000 1000 2
// 2 1000 2 1000 3 1000 1000
// 4 1000 1000 3 1000 1 1000
// 3 1 1000 1000 1 1000 2
// 1000 1000 2 1000 1000 2 1000
dijkstra(4);
for (auto v : dis) {
cout << v << " ";
}
cout << endl;
// 4 2 4 3 1000 1 3
return 0;
}