//Kruskal's algorithm
#include<bits//stdc++.h>
using namespace std;
#define pf printf
#define sf scanf
#define inf 999
int main()
{
int s=0;
pf("Enter no of nodes: \n");
int n ;
sf("%d",&n);
int a[n][n];
int c[n][n]= {0};
pf("Enter the weighted graph\nNote:999 for infinity\n");
for(int i = 0 ; i<n; i++)
for(int j = 0 ; j<n ; j++)
{
sf("%d",&a[i][j]);
c[i][j]=999;
}
pf("Given weighted graph is :\n");
for(int i = 0 ; i<n; i++)
{
for(int j = 0 ; j<n ; j++)
{
pf("%d ",a[i][j]);
}
pf("\n");
}
pf("\n");
int ti,tj,low;
for(int i =0 ; i<n-1; i++)
{
ti=inf;
tj=inf;
low=inf;
for(int l = 0; l<n; l++)
{
for(int m=0; m<n; m++)
{
if(low>a[l][m]&&(c[l][m]==999)&&a[l][m]!=0)
{
low =a[l][m];
ti=l;
tj=m;
}
}
}
c[ti][tj]=low;
c[tj][ti]=low;
//floyd's algo
for(int i = 0 ; i <n ; i++)
{
int tem[n][n];
for(int k = 0 ; k<n ; k++)
{
for(int l = 0 ; l<n ; l++)
{
int t = 0;
if(k==l)
{
tem[k][l]=0;
}
else if(k==i||l==i)
{
tem[k][l]=c[k][l];
}
else
{
t= c[k][i]+c[i][l];
if(t<c[k][l]&&c[k][l]!=0)
{
tem[k][l] = t;
}
else
{
tem[k][l] = c[k][l];
}
}
}
}
for(int i = 0 ; i<n; i++)
{
for(int j = 0 ; j<n ; j++)
{
c[i][j]=tem[i][j];
}
}
}
//floyd's algo
s=s+low;
pf("%d<->%d, %d\n",ti,tj,low);
}
pf("shortest path is %d\n",s);
return 0 ;
}
/*
6
0
4
4
999
999
999
4
0
2
999
999
999
4
2
0
3
1
6
999
999
3
0
999
2
999
999
1
999
0
3
999
999
6
2
3
0
*/
Ly9LcnVza2FsJ3MgYWxnb3JpdGhtCiNpbmNsdWRlPGJpdHMvL3N0ZGMrKy5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwojZGVmaW5lIHBmIHByaW50ZgojZGVmaW5lIHNmIHNjYW5mCiNkZWZpbmUgaW5mIDk5OQppbnQgbWFpbigpCnsKICAgIGludCBzPTA7CiAgICBwZigiRW50ZXIgbm8gb2Ygbm9kZXM6IFxuIik7CiAgICBpbnQgbiA7CiAgICBzZigiJWQiLCZuKTsKICAgIGludCBhW25dW25dOwogICAgaW50IGNbbl1bbl09IHswfTsKICAgIHBmKCJFbnRlciB0aGUgd2VpZ2h0ZWQgZ3JhcGhcbk5vdGU6OTk5IGZvciBpbmZpbml0eVxuIik7CiAgICBmb3IoaW50IGkgPSAwIDsgaTxuOyBpKyspCiAgICAgICAgZm9yKGludCBqID0gMCA7IGo8biA7IGorKykKICAgICAgICB7CiAgICAgICAgICAgIHNmKCIlZCIsJmFbaV1bal0pOwogICAgICAgICAgICBjW2ldW2pdPTk5OTsKICAgICAgICB9CiAgICBwZigiR2l2ZW4gd2VpZ2h0ZWQgZ3JhcGggaXMgOlxuIik7CiAgICBmb3IoaW50IGkgPSAwIDsgaTxuOyBpKyspCiAgICB7CiAgICAgICAgZm9yKGludCBqID0gMCA7IGo8biA7IGorKykKICAgICAgICB7CiAgICAgICAgICAgIHBmKCIlZCAiLGFbaV1bal0pOwogICAgICAgIH0KICAgICAgICBwZigiXG4iKTsKICAgIH0KICAgIHBmKCJcbiIpOwogICAgaW50IHRpLHRqLGxvdzsKICAgIGZvcihpbnQgaSA9MCA7IGk8bi0xOyBpKyspCiAgICB7CiAgICAgICAgdGk9aW5mOwogICAgICAgIHRqPWluZjsKICAgICAgICBsb3c9aW5mOwogICAgICAgIGZvcihpbnQgbCA9IDA7IGw8bjsgbCsrKQogICAgICAgIHsKICAgICAgICAgICAgZm9yKGludCBtPTA7IG08bjsgbSsrKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBpZihsb3c+YVtsXVttXSYmKGNbbF1bbV09PTk5OSkmJmFbbF1bbV0hPTApCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgbG93ID1hW2xdW21dOwogICAgICAgICAgICAgICAgICAgIHRpPWw7CiAgICAgICAgICAgICAgICAgICAgdGo9bTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBjW3RpXVt0al09bG93OwogICAgICAgIGNbdGpdW3RpXT1sb3c7CiAgICAgICAgLy9mbG95ZCdzIGFsZ28KICAgICAgICBmb3IoaW50IGkgPSAwIDsgaSA8biA7IGkrKykKICAgICAgICB7CiAgICAgICAgICAgIGludCB0ZW1bbl1bbl07CiAgICAgICAgICAgIGZvcihpbnQgayA9IDAgOyBrPG4gOyBrKyspCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGZvcihpbnQgbCA9IDAgOyBsPG4gOyBsKyspCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgaW50IHQgPSAwOwogICAgICAgICAgICAgICAgICAgIGlmKGs9PWwpCiAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICB0ZW1ba11bbF09MDsKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgZWxzZSBpZihrPT1pfHxsPT1pKQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgdGVtW2tdW2xdPWNba11bbF07CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgIHQ9IGNba11baV0rY1tpXVtsXTsKICAgICAgICAgICAgICAgICAgICAgICAgaWYodDxjW2tdW2xdJiZjW2tdW2xdIT0wKQogICAgICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICB0ZW1ba11bbF0gPSB0OwogICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgdGVtW2tdW2xdID0gY1trXVtsXTsKICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgICAgICBmb3IoaW50IGkgPSAwIDsgaTxuOyBpKyspCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGZvcihpbnQgaiA9IDAgOyBqPG4gOyBqKyspCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgY1tpXVtqXT10ZW1baV1bal07CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgLy9mbG95ZCdzIGFsZ28KICAgICAgICBzPXMrbG93OwogICAgICAgIHBmKCIlZDwtPiVkLCAlZFxuIix0aSx0aixsb3cpOwogICAgfQogICAgcGYoInNob3J0ZXN0IHBhdGggaXMgJWRcbiIscyk7CiAgICByZXR1cm4gMCA7Cn0KLyoKNgowCjQKNAo5OTkKOTk5Cjk5OQo0CjAKMgo5OTkKOTk5Cjk5OQo0CjIKMAozCjEKNgo5OTkKOTk5CjMKMAo5OTkKMgo5OTkKOTk5CjEKOTk5CjAKMwo5OTkKOTk5CjYKMgozCjAKKi8K