Pode usar o Floyd-Warshall sim. O Importante é que o programa passe no online judge.
Fórum