#include <iostream>
using namespace std;
int a[100][100], n, s;
struct node
{
int st;
int su;
int dis;
} vert[100];
int infinit = 1;
// functii
void printa()
{
for (int i = 1; i <= n; i++)
printf("%3d%3d%4d\n", vert[i].st, vert[i].su, vert[i].dis);
printf("\n ---------------- \n");
}
int curentX ()
{
int cx = 0, cmic = infinit;
for (int i = 1; i <= n; i++)
if (vert[i].st == 1 && vert[i].dis < cmic)
{ cx = i; cmic = vert[i].dis;}
return cx;
}
int main()
{
// read data
cin >> n >> s;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
cin >> a[i][j];
infinit += a[i][j];
}
// step 0 - initialization
for (int i =1; i <= n; i++)
vert[i].st = 0, vert[i].su = i, vert[i].dis = infinit;
vert[s].st = 1; vert[s].dis = 0;
// step 1
int x = curentX();
while (x != 0)
{
for (int y = 1; y <= n; y++)
if (a[x][y] > 0 && vert[y].st != 2)
{
int d = vert[x].dis + a[x][y];
if (d < vert[y].dis)
{
vert[y].st = 1;
vert[y].su = x;
vert[y].dis = d;
}
}
vert[x].st = 2;
x = curentX();
printa();
}
return 0;
}
--------------------------------------
14 2
0 10 1 0 0 0 0 0 4 0 0 0 0 0
10 0 0 0 0 0 0 0 0 0 0 0 5 0
1 0 0 0 0 0 0 0 8 0 0 0 7 0
0 0 0 0 0 0 0 0 7 2 0 3 0 4
0 0 0 0 0 9 10 8 0 1 7 0 0 0
0 0 0 0 9 0 2 0 0 0 16 0 0 0
0 0 0 0 10 2 0 8 0 0 0 0 0 0
0 0 0 0 8 0 8 0 30 0 0 0 0 15
4 0 8 7 0 0 0 30 0 0 0 0 0 2
0 0 0 2 1 0 0 0 0 0 0 0 0 6
0 0 0 0 7 16 0 0 0 0 0 15 0 0
0 0 0 3 0 0 0 0 0 0 15 0 12 0
0 5 7 0 0 0 0 0 0 0 0 12 0 0
0 0 0 4 0 0 0 15 2 6 0 0 0 0
#include <iostream>
using namespace std;
int a[100][100], dp[100][100], n, s;
int infinit = 1;
// functii
void printa()
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++) printf("%4d", dp[i][j]);
printf("\n");
}
printf("\n ---------------- \n");
}
int main()
{
// read data
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
cin >> a[i][j];
infinit += a[i][j];
}
// step 0 DP
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
if (a[i][j]) dp[i][j] = dp[j][i] = a[i][j];
else dp[i][j] = dp[j][i] = infinit;
printa();
// step 1 - general step
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
{
if ( dp[i][k] + dp[k][j] < dp[i][j])
dp[i][j] = dp[j][i] = dp[i][k] + dp[k][j];
}
printa();
return 0;
}