CompetitiveProgramming/FloydWarshal.cpp at master · naksh9619/CompetitiveProgramming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include<bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define INF 1e17
using namespace std;
const int mod=1e9+7;

ll exponentiation(ll base,ll power)
{
    ll ans=1;
    while(power>0)
    {
       if(power%2==1)
            ans=(ans*base)%mod;
       base=(base*base)%mod;
       power/=2;
    }
    return ans%mod;
}
inline int read_int()
{
    bool minus=false;
	int result=0;
	char ch;
	ch=getchar();
	while(true){
        if(ch=='-') break;
		if(ch>='0' && ch<='9') break;
		ch=getchar();
	}
	if(ch=='-') minus=true; else result=ch-'0';
	while(true){
		ch=getchar();
		if(ch<'0' || ch>'9') break;
		result=result*10+(ch-'0');
	}
	if(minus)
		return (-result);
	else
		return result;
}

inline ll read_long_long()
{
    bool minus=false;
	ll result=0;
	char ch;
	ch=getchar();
	while(true){
        if(ch=='-') break;
		if(ch>='0' && ch<='9') break;
		ch=getchar();
	}
	if(ch=='-') minus=true; else result=ch-'0';
	while(true){
		ch=getchar();
		if(ch<'0' || ch>'9') break;
		result=result*10+(ch-'0');
	}
	if(minus)
		return (-result);
	else
		return result;
}

ll edges,a,b,weight,t,n,dis[10][10];
//Undirected Graph
int main()
{
    for(int i=0;i<10;i++)
        for(int j=0;j<10;j++)
            dis[i][j]=INT_MAX;
    for(int i=0;i<10;i++)
        for(int j=0;j<10;j++)
            if(i==j) dis[i][j]=0;
    n=read_int();
    edges=read_int();
    while(edges--)
    {
        a=read_int();
        b=read_int();
        weight=read_int();
        dis[a][b]=weight;
        dis[b][a]=weight;//Comment this line to make it directed
    }
    for(int k=0;k<n;k++)
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                if(dis[i][k]+dis[k][j]<dis[i][j])
                    dis[i][j]=dis[i][k]+dis[k][j];
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cout<<dis[i][j]<<" ";
        cout<<endl;
return 0;
}