题目描述
spfa 模板题打卡
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
JAVA 代码
import java.util.*;
import java.lang.*;
class Main{
//n 和 m差不多是一个级别的用邻接表存储图
// 图结构
static int N = 2010;
static int M = 10010;
static int idx;
static int h[];
static int e[];
static int ne[];
static int w[];
static void addEdge(int a, int b,int c){
e[idx] = b;
ne[idx] = h[a];
w[idx] = c;
h[a] = idx++;
}
//最短距离
static int dist[];
static int cnt[];
static boolean st[];
static void init(int n, int m){
idx = 0;
//初始化每个节点的表头为没有边
h = new int [N];Arrays.fill(h,-1);
e = new int [M];
ne = new int [M];
w = new int[M]; //这条边的权值
//点最小距离数据
dist = new int [N];
st = new boolean[N];
cnt = new int [N];
while(m-->0)addEdge(sc.nextInt(),sc.nextInt(),sc.nextInt());
}
static boolean spfa_circle(int n, int m){
init(n,m);
Queue<Integer> q = new LinkedList<Integer>();
//将所有点进入队列
for(int i = 1;i <= n;i++){
q.add(i);
st[i] = true;
}
while(!q.isEmpty()){
int item = q.poll();
st[item] = false;
//找所有的边
for(int i=h[item];i != -1; i = ne[i]){
int j = e[i];
if(dist[j] > dist[item] + w[i]){
dist[j] = dist[item] + w[i];
cnt[j] = cnt[item] + 1;
if(cnt[j] >= n) {
return true;
}
if(!st[j]){
q.add(j);
st[j] = true;
}
}
}
}
return false;
}
static Scanner sc = new Scanner(System.in);
public static void main(String[]args){
System.out.println(spfa_circle(sc.nextInt(),sc.nextInt())?"Yes":"No");
}
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla