INOI1402 | Editorial by aksingh007

This problem is reduced to find the all pair shortest path. It can be solved in O(n^3) using floyd Warshall's (learn [here](https://www.geeksforgeeks.org/floyd-warshall-algorithm-dp-16/) in details). Print the maximum of all pair shortest path.

```
#include<stdio.h>
#include<stdlib.h>
#define LL long long
#define or ||
#define and &&
#define s(n) scanf("%lld",&n)
#define p(n) printf("%lld ",n)

//int adj[100][100];
LL int spath[232][232];
int main(){
	LL int i,j,k,n,p,f,max=-111;
	s(n);
	s(f);
	for(i=1;i<=n;i++){
	for(j=1;j<=n;j++){
	    spath[i][j]=10000000000000;
	}
	}
	while(f--){
		s(i);s(j);s(p);
		spath[i][j]=p;
		spath[j][i]=p;
	}
	
for(k=1;k<=n;k++){
 for(i=1;i<=n;i++){
  for(j=1;j<=n;j++)
   spath[i][j]=(spath[i][j]>(spath[i][k]+spath[k][j]))?(spath[i][k]+spath[k][j]):spath[i][j];
	}
}
/*printf("   $$$$$$$$$$   \n");
for(i=1;i<=n;i++){
	for(j=1;j<=n;j++)
	p(spath[i][j]);
printf("\n");
}*/

for(i=1;i<=n;i++){
	for(j=i+1;j<=n;j++){
		if(spath[i][j]>max)
			max=spath[i][j];
	}
}
printf("%d",max);
return 0;
}
		
		
```

INOI1402 | Editorial by aksingh007

Download submission

All caught up!

View submission

Is your resume even shortlisted?