ワーシャルフロイド法を使って始点からのポテンシャルを求め、それをもとにダイクストラ法で最短経路問題を解いても多項式時間でできますね