关注
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
相关推荐
06-09 11:12
重庆移通学院 运营 不要停下啊:大二打开牛客,你有机会开卷了,卷起来
,去找课程学习,在牛客上看看大家面试笔试都需要会什么,岗位有什么需求就去学什么,努力的人就一定会有收获,这句话从来都经得起考验,像我现在大三了啥也不会,被迫强行考研,炼狱难度开局,啥也不会
,找工作没希望了,考研有丝丝机会
点赞 评论 收藏
分享
06-16 19:09
河南开封科技传媒学院 Java 
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 第一份工作应该选高薪还是热爱? #
67156次浏览 594人参与
# 不考虑薪资和职业,你最想做什么工作呢? #
92287次浏览 680人参与
# 秋招签约后的心态变化 #
82748次浏览 814人参与
# 听劝,这个公司值得去吗 #
486516次浏览 1705人参与
# 你觉得早上几点上班合适? #
72580次浏览 303人参与
# 学历贬值真的很严重吗? #
24741次浏览 174人参与
# 机械人与华为的爱恨情仇 #
120324次浏览 957人参与
# 一人推荐一个值得去的通信/硬件公司 #
186674次浏览 1859人参与
# 打工人的工作餐日常 #
53500次浏览 418人参与
# 哪些公司真双非友好? #
15960次浏览 82人参与
# 26届的你们有几段实习? #
45018次浏览 492人参与
# 月薪多少能在一线城市生存 #
29579次浏览 311人参与
# 双非能在秋招上岸吗? #
221897次浏览 1172人参与
# 你以为的实习VS真实的实习 #
30840次浏览 276人参与
# 今年秋招哪家公司给的薪资最良心? #
253213次浏览 1419人参与
# 你后悔自己读研吗? #
21238次浏览 240人参与
# 当下环境,你会继续卷互联网,还是看其他行业机会 #
118116次浏览 812人参与
# 追觅科技求职进展汇总 #
18409次浏览 120人参与
# 实习想申请秋招offer,能不能argue薪资 #
150178次浏览 933人参与
# 如何KTV领导 #
62941次浏览 472人参与