关注
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
相关推荐
程序员小白条:呃呃呃,都还没面试,我都不会问这么细,何况通不通过,去不去都另说,你没实力和学历的话,在外面就这样,说实话没直接已读不回就不错了,浪费时间基本上
点赞 评论 收藏
分享
05-21 14:50
湖南机电职业技术学院 前端工程师 nus2201602...:兄弟,你这个简历撕了丢了吧,就是一坨,去找几个项目,理解项目流程,看几遍就是你的了,看看八股就去干了,多看看牛客里别人发出来的简历,对着写,你这写的啥啊,纯一坨

点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 实习生的蛐蛐区 #
30075次浏览 219人参与
# 说说你知道的学历厂 #
21399次浏览 127人参与
# 计算机有哪些岗位值得去? #
10138次浏览 90人参与
# 你找工作的时候用AI吗? #
12112次浏览 133人参与
# 应届生,你找到工作了吗 #
16029次浏览 131人参与
# 面试尴尬现场 #
17606次浏览 111人参与
# 下班后的时间你怎么安排 #
5611次浏览 62人参与
# 社会教会你的第一课 #
23475次浏览 294人参与
# 哪一瞬间觉得自己长大了 #
5641次浏览 100人参与
# 你认为小厂实习有用吗? #
8445次浏览 85人参与
# 电网笔面经互助 #
36063次浏览 351人参与
# 职场中对你有帮助的书 #
17426次浏览 203人参与
# 学历贬值真的很严重吗? #
21789次浏览 161人参与
# 双非应该如何逆袭? #
188027次浏览 3404人参与
# 简历当中有水分算不算造假? #
20311次浏览 235人参与
# 神州信息工作体验 #
15673次浏览 67人参与
# 现在前端的就业环境真的很差吗 #
294664次浏览 3568人参与
# 哪些公司校招卡第一学历 #
61936次浏览 234人参与
# 毕业旅行去哪玩儿 #
12308次浏览 133人参与
# 求职遇到的搞笑事件 #
119509次浏览 791人参与