> 有一个问题，这个题目似乎没有保证一个图中所有的节点都是联通的；
> 如果该图有多个联通分量，且负环不在节点1所在的联通分量中，您这种方法似乎就行不通了啊。
> 不过AC了，是不是题目数据太水

Add a new vertex s with 0-weight edges to each of the vertices through v1 to vn. Run the Bellman-Ford algorithm on this graph with s as the source vertex, and use the result to determine whether it contains a negative cycle.