kama94.Bellman_ford
public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();int m = scan.nextInt();//初始化int[][] edges = new int[m][3];int[][] graph = new int[n+1][n+1];for(int i=0;i<=n;i++) {Arrays.fill(graph[i], Integer.MAX_VALUE);}int[] minDp = new int[n+1];Arrays.fill(minDp, Integer.MAX_VALUE);//接收数据for(int i=0;i<m;i++) {int x = scan.nextInt();int y = scan.nextInt();int val = scan.nextInt();graph[x][y]=val;edges[i][0]=x;edges[i][1]=y;edges[i][2]=val;}//松弛操作minDp[1]=0;for(int i=0;i<n;i++) {for(int j=0;j<m;j++) {int[] edge = edges[j];if(minDp[edge[0]]!=Integer.MAX_VALUE&&minDp[edge[1]]>minDp[edge[0]]+edge[2]) {minDp[edge[1]]=minDp[edge[0]]+edge[2];}}}//输出if(minDp[n]==Integer.MAX_VALUE) System.out.println("unconnected");else System.out.println(minDp[n]);scan.close();}
