格式：x-rar 资源大小：8.1MB
SPFA+Dijkstra+Floyd Java模板模板
SPFA
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class SPFA {
static SE[] e = new SE[9999];
static int[] dis = new int[9999];
static int[] head = new int[9999];
static boolean[] vis = new boolean[9999];
static int[] cnt = new int[9999]; //表示到达i点经历的点的个数 用来判断是否存在环
static int n,m;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(true) {
n = sc.nextInt();
m = sc.nextInt();
if(n==0&&m==0) break;
Arrays.fill(e, null);
Arrays.fill(head, 0);
int len = 1;
for(int i=0;i<m;i++) {
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
e[len] = new SE();
e[len].add(b, c, head[a]);
head[a] = len++;
e[len] = new SE();
e[len].add(a, c, head[b]);
head[b] = len++;
}
if(!spfa(1)) {
System.out.println("YES"+dis[n]);
}else {
System.out.println("NO");
}
}
}
public static boolean spfa(int s) {
Arrays.fill(vis, false);
Arrays.fill(dis, 99999);
Arrays.fill(cnt, 0);
dis[s] = 0;
Queue q = new LinkedList();
q.offer(s);
while(!q.isEmpty()){
int u = q.poll();
vis[u] = false;
for(int i=head[u];i!=0;i=e[i].next) {
int v = e[i].v;
int w = e[i].w+dis[u];
if(dis[v]>w) {
dis[v] = w;
cnt[v] = cnt[u]+1;
if(cnt[v]>=n) return true; //表示存在环
if(!vis[v]) {
vis[v] = true;
q.offer(v);
}
}
}
}
return false;
}
资源评论
weixin_38688371
- 粉丝: 7
最新资源
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
