关注
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-08 12:45
吉林大学 硬件开发 现在深挖技术还来得及:大厂
我这个地方基本部门组里就我一个 同事要不出差 要不就是另一个地方办公
实习搭子来的第二周就去上海出差了,到现在还没回来
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 计算机有哪些岗位值得去? #
9346次浏览 88人参与
# 电网笔面经互助 #
35957次浏览 348人参与
# 实习生的蛐蛐区 #
28421次浏览 216人参与
# 听劝,这个简历怎么改 #
177380次浏览 1150人参与
# 应届生,你找到工作了吗 #
15394次浏览 127人参与
# 你找工作的时候用AI吗? #
11007次浏览 103人参与
# 说说你知道的学历厂 #
20055次浏览 120人参与
# 总结:哪家公司面试体验感最好 #
51501次浏览 367人参与
# 学历贬值真的很严重吗? #
21668次浏览 161人参与
# 面试尴尬现场 #
15724次浏览 102人参与
# 入职第一天,你准备什么时候下班 #
62867次浏览 380人参与
# 大学生该如何认清当下的就业环境? #
88691次浏览 567人参与
# 下班后的时间你怎么安排 #
5067次浏览 57人参与
# 打工人的工作餐日常 #
48607次浏览 362人参与
# 哪些公司校招卡第一学历 #
61820次浏览 234人参与
# 哪一瞬间觉得自己长大了 #
5230次浏览 86人参与
# 社会教会你的第一课 #
21703次浏览 272人参与
# 你认为小厂实习有用吗? #
7989次浏览 80人参与
# 你觉得第一学历对求职有影响吗? #
92900次浏览 668人参与
# 研究所笔面经互助 #
75401次浏览 470人参与