POJ1724最短路

本文主要是介绍POJ1724最短路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

n个点，拥有总的价值money
m条边（u，v,len ,cost），长度len，代价cost
求不超过money的代价条件下最短路。

public class Main {public static void main(String[] args) {new Task().solve();}
}class Task {InputReader in = new InputReader(System.in);PrintWriter out = new PrintWriter(System.out);class Edge implements Comparable<Edge>{int v , cost , len ;Edge(int v , int len , int cost) {this.v = v ;this.len = len ;this.cost = cost ;}@Overridepublic int compareTo(Edge o) {if(len == o.len) return (cost < o.cost) ? -1 : ((cost == o.cost) ? 0 : 1) ;return (len < o.len) ? -1 : ((len == o.len) ? 0 : 1) ;}}List<Edge>[] adj  ;int bfs(int start , int end , int money){Queue<Edge> q = new PriorityQueue<Edge>() ;q.add(new Edge(start , 0 , 0)) ;while(! q.isEmpty()){Edge now = q.poll() ;if(now.v == end) return now.cost <= money ? now.len : -1 ;for(Edge next : adj[now.v]){if(now.cost + next.cost <= money)q.add(new Edge(next.v , now.len+next.len , now.cost + next.cost)) ;}}return -1 ;}void solve() {int cost = in.nextInt() ;int n = in.nextInt() ;int m = in.nextInt() ;adj = new List[n+1] ;for(int i = 1 ; i <= n ; i++) adj[i] = new ArrayList<Edge>() ;while(m-- > 0){adj[in.nextInt()].add(new Edge(in.nextInt() , in.nextInt() , in.nextInt())) ;}out.println(bfs(1 , n , cost)) ;out.flush();}}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());}}

这篇关于POJ1724最短路的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---