import java.util.ArrayList;import java.util.LinkedList;import java.util.Scanner; public class Main { public static void main(String[] args) { new Main().solve(); } private void solve() { Scanner scanner = new Scanner(System.in); int n = 6; int adj[][] = new int[n][n]; for (int i = 0; i < n; i++) { String[] strings= scanner.nextLine().split(" "); for (int j = 0; j < n; j++) { adj[i][j] =Integer.valueOf(strings[j]); } } Graph graph = new Graph(adj); graph.bfs(0); } static class Graph { int[][] adj; int nVerts; boolean[] visited; private Graph(int[][] adj) { this.adj = adj; this.nVerts = adj.length; this.visited = new boolean[nVerts]; } private void bfs(int start) { int[] dis=new int[nVerts]; for (int i = 0; i < nVerts; i++) { dis[i]=Integer.MAX_VALUE; } visited[start] = true; LinkedList<Integer> queue = new LinkedList<>(); queue.add(start); dis[start]=0; while (!queue.isEmpty()) { int v = queue.remove(); ArrayList<Integer> vs; vs =getNextVertex(v); for (Integer v1:vs){ int distance=adj[v][v1]; if (distance+dis[v]<dis[v1]) dis[v1]=distance+dis[v]; if (!visited[v1]) { queue.add(v1); visited[v1] = true; } } } for (int i = 0; i <nVerts; i++) { if (i!=0){ System.out.println(dis[i]); } } } private ArrayList<Integer> getNextVertex(int v) { ArrayList<Integer> adjVs = new ArrayList<>(); for (int i = 0; i < adj.length; i++) { if (i!=v&&adj[v][i] != -1) adjVs.add(i); } return adjVs; } }}
点赞 1

相关推荐

不愿透露姓名的神秘牛友
07-07 12:04
毕业生招你惹你了,问一个发薪日来一句别看网上乱七八糟的你看哪个工作没有固定发薪日扭头就取消了面试就问了一句公司都是这个态度吗还搞上人身攻击了...
程序员小白条:呃呃呃,都还没面试,我都不会问这么细,何况通不通过,去不去都另说,你没实力和学历的话,在外面就这样,说实话没直接已读不回就不错了,浪费时间基本上
点赞 评论 收藏
分享
nus2201602...:兄弟,你这个简历撕了丢了吧,就是一坨,去找几个项目,理解项目流程,看几遍就是你的了,看看八股就去干了,多看看牛客里别人发出来的简历,对着写,你这写的啥啊,纯一坨
点赞 评论 收藏
分享
06-10 23:36
已编辑
首都经济贸易大学 C++
点赞 评论 收藏
分享
牛客网
牛客网在线编程
牛客网题解
牛客企业服务