import ;
import ;
import ;
import ;
import ;
import ;
import ;
public class test4 {
static HashMap<Integer, LinkedList<Pair<Integer, Integer>>> graph = new HashMap<>();//存储原始图
static Scanner scanner = new Scanner(System.in);
static int v, e;//顶点数，边数
static int[] pre, dis, visted;//存储前节点和距离
@SuppressWarnings({ "unchecked", "rawtypes" })
public static void ini() {
("请输入顶点数：");
v = ();
("请输入边数和各条边以及权重：");
e = ();
pre = new int[v];
dis = new int[v];
for(int i=0; i<v; i++) {
pre[i] = -1;
dis[i] = 1000;
}
for(int i=0; i<e; i++) {
(i, new LinkedList<>());
}
for(int i=0; i<e; i++) {
int from = ();
int to = ();
int weight = ();
graph.get(from).add(new Pair(to, weight));//有向图
//graph.get(to).add(new Pair(from, weight));//双向添加
//DFS(from, visited, graph);
}
printGraph(graph);
}
//输出图
public static void printGraph(HashMap<Integer, LinkedList<Pair<Integer, Integer>>> graph) {
for(int i=0; i<v; i++) {
("\n"+i+" : ");
for(Pair<Integer, Integer> p : graph.get(i)) {
(" "+i+"->"+()+" "+());//i->p 3
}
}
();;
}
//relax操作
public static void relax(int i, Pair<Integer, Integer> pair) {
int from = i, to = (), weight = ();
int newD = dis[from]+weight;
if(dis[to] > newD) {
dis[to] = newD;
pre[to] = from;
}
}
//beelman-ford
public static void bellman_ford(HashMap<Integer, LinkedList<Pair<Integer, Integer>>> graph, int s) {
dis[s] = 0;//源点到自己的距离是0；
for(int i=0; i<v-1; i++) {
for(int j=0; j<v; j++) {
for(Pair<Integer, Integer> pair:graph.get(j)) {//每一个点的linkedList
relax(j, pair);
}
}
}
//验证有无负环
for(int j=0; j<v; j++) {
for(Pair<Integer, Integer> pair:graph.get(j)) {//每一个点的linkedList
if(dis[()] > dis[j]+()) {//
findCir(());
System.exit(0);
}
}
}
}
//根据点找负环，一直找pre，直到找到跟起点重合，则为一个负环
public static void findCir(int u) {
List<Integer> res = new LinkedList<>();
int end = pre[u];
//(u+" ");
for(int a:pre)
(a+" ");
while(true) {
if(end==-1)
continue;
if((end)!=-1)//查找到了
break;
res.add(end);
end = pre[end];
}
if(res.size()>0) {
("图中存在负环：");
for(int i=0; i<res.size(); i++)
(res.get(i)+"-> ");
} else
("图中没有负环");
}
public static void main(String[] args) {
// TODO Auto-generated method stub
ini();//初始化
bellman_ford(graph, 0);
}