本文主要是介绍poj 3259 最短路负环，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
John的农场里N块地，M条路连接两块地，W个虫洞，虫洞是一条单向路，会在你离开之前把你传送到目的地，就是当你过去的时候时间会倒退Ts。我们的任务是知道会不会在从某块地出发后又回来，看到了离开之前的自己。简化下，就是看图中有没有负权环。有的话就是可以，没有的话就是不可以了。
import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;public class Main {public static void main(String[] args) {new POJ3259().solve();}
}class POJ3259 {InputReader in = new InputReader(System.in) ;PrintWriter out = new PrintWriter(System.out) ;final int N = 508 ;final int M = 2500*3 ;final int inf = Integer.MAX_VALUE ;class Edge{int v ;int w ;int next ;Edge(int v , int w , int next) {this.v = v ;this.w = w ;this.next = next ;}}int n ; int[] head = new int[N] ; Edge[] e = new Edge[M] ; int eid ;int[] dist = new int[N] ;boolean[] inq = new boolean[N] ;int[] cnt = new int[N] ;void add(int u , int v , int w){e[eid] = new Edge(v , w , head[u]) ;head[u] = eid++ ;}void solve(){int t = in.nextInt() ;while(t-- > 0){n = in.nextInt() ;int m = in.nextInt() ;int w = in.nextInt() ;eid = 0 ;Arrays.fill(head , 1 , n+1 , -1) ;while(m-- > 0){int u = in.nextInt() ;int v = in.nextInt() ;int c = in.nextInt() ;add(u, v, c) ;add(v, u, c) ;}while(w-- > 0){add(in.nextInt() , in.nextInt() , -in.nextInt()) ;}Arrays.fill(dist , 1 , 1+n , inf) ;int res = -1 ;for(int i = 1 ; i <= n ; i++){if(dist[i] == inf){if(! spfa(i)){res = i ; break ;}}}out.println(res == -1 ? "NO" : "YES") ;}out.flush() ;}boolean spfa(int start){Arrays.fill(cnt, 1 , 1+n , 0) ;Arrays.fill(inq , 1 , 1+n , false) ;Queue<Integer> q = new LinkedList<Integer>() ;q.add(start) ;inq[start] = true ;dist[start] = 0 ;while(! q.isEmpty()){int u = q.poll() ;inq[u] = false ;if(cnt[u] >= n) return false ;for(int i = head[u] ; i != -1 ; i = e[i].next){int v = e[i].v ;int w = e[i].w ;if(dist[v] > dist[u] + w){dist[v] = dist[u] + w ;if(! inq[v]){inq[v] = true ; cnt[v]++ ;q.add(v) ;}}}}return true ;}
}class InputReader {public BufferedReader reader;public StringTokenizer tokenizer;public InputReader(InputStream stream) {reader = new BufferedReader(new InputStreamReader(stream), 32768);tokenizer = new StringTokenizer("");}private void eat(String s) {tokenizer = new StringTokenizer(s);}public String nextLine() {try {return reader.readLine();} catch (Exception e) {return null;}}public boolean hasNext() {while (!tokenizer.hasMoreTokens()) {String s = nextLine();if (s == null)return false;eat(s);}return true;}public String next() {hasNext();return tokenizer.nextToken();}public int nextInt() {return Integer.parseInt(next());}public long nextLong() {return Long.parseLong(next());}public double nextDouble() {return Double.parseDouble(next());}public BigInteger nextBigInteger() {return new BigInteger(next());}}
这篇关于poj 3259 最短路负环的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
