Winter Vacation Training Day 1 (01.26)

Area 2.1 : Floyd

Figure 3.1 : Floyd
Floyd is an algorithm sloving MSSP(multi source shortest path) problem.
It means that we can know the shortest path between (u, v).
The core of the algorithm is relax(u, v).

relax(u, v) = dist[v] -> min(dist[v], dist[u]+weight[u, v])
A relax operate can find current mininum sp.

Template:

for (int t=0;t<V;t++) {
    for (int i=0;i<V;i++) {
        for (int j=0;j<V;j++) {
            dist[i][j] = min(dist[i][j], dist[i][t]+dist[t][j]);
        }
    }
}

Given Score :
    Difficulty : 1
x   Basic Score : 14
Score : 166