【文件属性】：
文件名称：蓝桥杯(java)最短路
文件大小：1KB
文件格式：TXT
更新时间：2021-03-29 08:32:55
SPFA算法
import java.util.*;
public class Main {
public static long []daan;
public static void main(String []args){
Scanner ner=new Scanner(System.in);
int n=ner.nextInt();//顶点总数
int p=ner.nextInt();//边的数量
edge[]A=new edge[p];
//输入顶点之间的关系，不包括0，列如：1 2 3 1是开始顶点，2是到达顶点,3是所用距离
for(int i=0;i
list=new ArrayList();
daan=new long[n];
boolean []used=new boolean[n];
int []num=new int[n];
for (int i = 0; i < daan.length; i++) {
daan[i]=Integer.MAX_VALUE;
used[i]=false;
}
daan[s]=0;
used[s]=true;
num[s]=1;
list.add(s);
while(list.size()!=0)
{
int a=list.get(0);
list.remove(0);
for(int i=0;idaan[A[i].a]+A[i].value)
{
daan[A[i].b]=daan[A[i].a]+A[i].value;
if(!used[A[i].b])
{
list.add(A[i].b);
num[A[i].b]++;
if(num[A[i].b]>n)
return false;
used[A[i].b] = true;
}
}
}
used[a] = false;
}
return true;
}
}
class edge{
public int a;//边的起点
public int b;//边的终点
public int value;//之间的距离
edge(int a,int b,int value)
{
this.a=a;
this.b=b;
this.value=value;
}
}
