关于一个图论问题IDEA的求助

整体思路：给定一个有向连通图并指定一个源点s，保证这个点可以到达其他任意一个节点。将从s到各其它节点的所有最短路方案中所包括的路径所构成的一个子图称为这个图关于s的最短路子图。现在可以给原图中属于这个子图上的任意数量的边分别增加任意的正整数权值，使得原图修改后关于s的最短路子图仍包含相同的边，问最多共能增加多少的权值。保证在最初的图中没有负环，但不保证没有零环或负边。 现在并不知道这个问题是否可解。。。也不知道解法该是什么样子。。。数据范围什么的就更别说了