I've implemented the Floyd Warshall algorithm in this problem. However, as this is my first time in handling with adjacency list, I was not able to make it memory efficient.
I used a 1000*1000 and another list of 1000 size but I have seen solutions of people getting accepted with 100*100 size. How can I make my graph array size less, or perhaps what is the best possible way to accept input in the adjacency list in graph?
P.S.: I tried using vector and map/pairs STL, but since I am not good in STL, I will be more than happy if a non STL solution is presented.
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
#define INF 1e9
int graph[1000][1000], m[1001], n; //this is the array which I want to decrease
int main(){
int u, v, flag=0, testCase = 1;
while(scanf("%d%d", &u, &v), u||v){
n = 0;
memset(m, 0, sizeof(m));
for(int i = 0; i < 1000; i++)
for(int j=0; j<1000; j++)
graph[i][j] = INF;
if(!m[u])
m[u] = ++n;
if(!m[v])
m[v] = ++n;
graph[m[u]][m[v]] = 1;
graph[m[u]][m[u]] = 0;
graph[m[v]][m[v]] = 0;
while(scanf("%d%d", &u, &v), u||v){
if(!m[u])
m[u] = ++n;
if(!m[v])
m[v] = ++n;
graph[m[u]][m[v]] = 1;
graph[m[u]][m[u]] = 0;
graph[m[v]][m[v]] = 0;
}
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
double s = 0.0;
for(int i = 1; i <= n; i++)
for(int j=1; j<=n; j++)
s += graph[i][j];
//cout<<s<<endl;
s /= (double)n*(n-1);
//cout<<s<<endl;
printf("Case %d: average length between pages = %.3lf clicks\n",testCase++,s);
}
return 0;
}
Running here