AcWing 851. spfa求最短路 Java
原题链接
简单
作者:
leo_0
,
2020-07-28 15:31:01
,
所有人可见
,
阅读 344
题目描述
算法1
Java 代码
import java.util.*;
import java.io.*;
public class Main{
static class Edge{
int x,y,d;
public Edge(int x, int y, int d){
this.x = x;
this.y = y;
this.d = d;
}
}
static final int INF = Integer.MAX_VALUE >> 1;
static int n,m;
// 稀疏图 邻接表
static List<List<Edge>> graph = new ArrayList<>();
static int[] dist, cnt;
static boolean[] st;
public static void main(String[] args) throws IOException{
BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
String[] s = cin.readLine().split("\\s+");
n = Integer.parseInt(s[0]);
m = Integer.parseInt(s[1]);
st = new boolean[n];
dist = new int[n];
cnt = new int[n];
for(int i= 0;i < n; i++){
graph.add(new ArrayList<Edge>());
}
while(m--> 0){
String[] s1 = cin.readLine().split("\\s+");
int x = Integer.parseInt(s1[0]) - 1;
int y = Integer.parseInt(s1[1]) - 1;
int z = Integer.parseInt(s1[2]);
graph.get(x).add(new Edge(x, y, z));
}
boolean ans = spfa();
if(ans){
System.out.println("Yes");
}else{
System.out.println("No");
}
}
static boolean spfa(){
// 初始化距离
Arrays.fill(dist, INF);
dist[0] = 0;
Queue<Integer> q = new LinkedList<>();
// 注意把所有点都放进去
for(int i = 0;i < n;i++){
q.add(i);
st[i]=true;
}
st[0] = true;
while(!q.isEmpty()){
int x = q.poll();
st[x] = false;
List<Edge> edges = graph.get(x);
for (int i = 0 ; i < edges.size(); i ++){
Edge edge = edges.get(i);
int y = edge.y;
if (dist[y] > dist[x] + edge.d ){
dist[y] = dist[x] + edge.d;
cnt[y] = cnt[x] + 1;
if(cnt[y] >= n) return true;
if(!st[y]){
q.add(y);
st[y] = true;
}
}
}
}
return false;
}
}
踩