判负环就是看入队次数>n
import java.util.Queue; import java.util.Scanner; import java.util.concurrent.LinkedBlockingDeque; public class Main { static class Edge{ int v,w,next; Edge(int v,int w,int next){ this.v=v; this.w=w; this.next=next; } } static final int N= 100500; static final int M=1000050; static final int INF=0x3f3f3f3f; static int n,m,s,t,u,v,w,cnt; static int[] head=new int[N]; static Edge[] edges=new Edge[M]; static int[] dis=new int[N]; static boolean[] vis=new boolean[N]; static int[] inq=new int[N]; static void init(){ cnt=0; for(int i=1;i<=n;i++){ head[i]=-1; } } static void addEdge(int u,int v,int w){ edges[cnt]=new Edge(v,w,head[u]); head[u]=cnt++; edges[cnt]=new Edge(u,w,head[v]); head[v]=cnt++; } static boolean spfa(){ for(int i=1;i<=n;i++){ vis[i]=false; inq[i]=0; dis[i]=INF; } dis[s]=0; vis[s]=true; Queue<Integer> q=new LinkedBlockingDeque<>(); q.add(s); inq[s]=1; while(!q.isEmpty()){ int u=q.poll(); vis[u]=false; for(int i=head[u];i!=-1;i=edges[i].next){ int v=edges[i].v; int w=edges[i].w; if(dis[v]>dis[u]+w){ dis[v]=dis[u]+w; if(!vis[v]){ vis[v]=true; q.add(v); if(++inq[v]>n){ return false; } } } } } return true; } public static void main(String[] args) { Scanner cin=new Scanner(System.in); n=cin.nextInt(); m=cin.nextInt(); s=cin.nextInt(); t=cin.nextInt(); init(); while(m-->0){ u=cin.nextInt(); v=cin.nextInt(); w=cin.nextInt(); addEdge(u,v,w); } spfa(); System.out.println(dis[t]); } }