java模板系列之spfa

java模板系列之spfa

最优情况下，时间复杂度是km，k是一个很小的常数，不过现在的出题人，都喜欢随手卡spfa，时间复杂度最差会到nm

//
// Source code recreated from a .class file by IntelliJ IDEA
// (powered by FernFlower decompiler)
//import java.util.*;public class Main {static List<v> a[];static int n,m;static int d[];static boolean v[];static int num[];static class v{int to,val;public v(int to, int val) { = to;this.val = val;}}static void spfa(){Arrays.fill(d,1000000009);Arrays.fill(v,false);Arrays.fill(num,0);Queue<Integer> q = new ArrayDeque<Integer>();d[1] = 0;v[1] = true;q.add(1);while(q.size()!=0){int x = q.poll();v[x] = false;for(int i=0;i<a[x].size();i++){int newto = a[x].get(i).to;int newval = a[x].get(i).val;if(d[newto]>d[x]+newval){d[newto]=d[x]+newval;if(!v[newto]){q.add(newto);v[newto] = true;}num[newto]++;if(num[newto]>=n){System.out.println("负环");}}}}}public static void main(String[] args) {Scanner input = new Scanner(System.in);while(input.hasNext()){n = Int();m = Int();d = new int[n+1];v = new boolean[n+1];num = new int[n+1];if(n == 0 && m == 0){break;}a = new List[n+1];for(int i=1;i<=n;i++){a[i] = new ArrayList<v>();}for(int i=0;i<m;i++){int from,to,val;from = Int();to = Int();val = Int();a[from].add(new v(to,val));a[to].add(new v(from,val));}spfa();System.out.println(d[n]);}}}