【笔记】数据结构与算法之最短路算法（SPFA）
这是bellmanFord算法的优化版本，还是比较好用的public class Main {
private static int N= 1000010; static int n,m;
static int idx = 1;
static int [] h = new int,ne = new int,e = new int, w = new int;
// distance 距离
static int [] dist = new int;
static int INF= 0x3f3f3f3f;
//statue判断当前的点是不是最终确定的最短点
staticboolean [] st = new boolean;
staticint [] arr = new int;
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String[] s = bf.readLine().split(" ");
// n个点m条边
n = Integer.parseInt(s);
m = Integer.parseInt(s);
Arrays.fill(h,-1);
for (int i = 0; i < m; i++) {
String []re = bf.readLine().split(" ");
//分别是第一条边和第二条边
int a = Integer.parseInt(re);
int b = Integer.parseInt(re);
//距离
int c = Integer.parseInt(re);
add(a,b,c);
}
int res = spfa();
if (res==-1) {
System.out.println("impossible");
}else {
System.out.println(res);
}
}
static void add(int a, int b, int c){
//当前的idx的element是b
e = b;
//当前的idx的权重是c
w = c;
//当前的idx的next是head
ne = h;
h = idx++;
}
private static int spfa() {
Arrays.fill(dist,INF);
dist = 0;
Queue<Integer> queue = new LinkedList<>();
queue.add(1);
st = true;
// int head = 0,tail = -1;
// arr[++tail] = 1;
// while (head<=tail){
// int temp = arr;
// st = false;
// for (int i = h;i!=-1;i= ne){
// int j = e;
// if (dist>dist+w){
// dist = dist+w;
// if (!st){
// st = true;
// arr[++tail] = j;
// }
// }
// }
// }
while (!queue.isEmpty()){
//弹出一个值 把这个值设置为不可用
int temp = queue.poll();
st = false;
//i从弹出的值开始遍历
for (int i = h;i!=-1;i= ne){
int j = e;
if (dist>dist+w){
dist = dist+w;
//如果j没用过，加入队列（加速）
if (!st){
st = true;
queue.add(j);
}
}
}
}
if (dist!=INF){
return dist;
}
return -1;
}
}
在新标签打开所有链接复制所有链接URL复制所有链接URL（反向）复制所有链接标题 + URL复制所有链接标题 + URL (MD)复制所有链接标题 + URL (BBS)复制所有链接标题 + URL (筛选)复制所有链接标题 + URL (设置复制格式)在新标签页打开所有图片链接在一个标签页显示所有图片链接
复选框 - 选中
复选框 - 取消
复选框 - 反选
单选框 - 选中
单选框 - 取消
特殊单选框 - 选中
在新标签打开所有链接复制所有链接URL复制所有链接URL（反向）复制所有链接标题 + URL复制所有链接标题 + URL (MD)复制所有链接标题 + URL (BBS)复制所有链接标题 + URL (筛选)复制所有链接标题 + URL (设置复制格式)在新标签页打开所有图片链接在一个标签页显示所有图片链接
复选框 - 选中
复选框 - 取消
复选框 - 反选
单选框 - 选中
单选框 - 取消
特殊单选框 - 选中 学习一下 谢谢分享 研究一下代码 :lol 站里Java的内容也太少了把
amose 发表于 2021-1-3 21:44
站里Java的内容也太少了把
主要还是Python和易语言
页:
[1]