计蒜客 Skiing 最长路

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

In this winter holiday, Bob has a plan for skiing at the mountain resort.

This ski resort has $M$ different ski paths and $N$ different flags situated at those turning points.

The $i$ -th path from the $S_i$ -th flag to the $T_i$ -th flag has length $L_i$ .

Each path must follow the principal of reduction of heights and the start point must be higher than the end point strictly.

An available ski trail would start from a flag, passing through several flags along the paths, and end at another flag.

Now, you should help Bob find the longest available ski trail in the ski resort.

Input Format

The first line contains an integer $T$ , indicating that there are $T$ cases.

In each test case, the first line contains two integers $N$ and $M$ where $\leq 10000$ and $\leq 100000$ as described above.

Each of the following $M$ lines contains three integers $S_i$ , $T_i$ , and $L_i~(0 < L_i < 1000)$ describing a path in the ski resort.

Output Format

For each test case, ouput one integer representing the length of the longest ski trail.

样例输入

样例输出

题目来源

2017 ACM-ICPC 亚洲区（乌鲁木齐赛区）网络赛

入度为0的点u，添加虚拟边（0 , u , 0）。单源（源点为0）最短路。

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 Task().solve();}
}class Task {InputReader in = new InputReader(System.in) ;PrintWriter out = new PrintWriter(System.out) ;final int N = 10008 ;  final int M = 100008 * 2 ;  int[] head = new int[N] ;class Edge{int v , w , next ;Edge(int v , int w , int next) {this.v = v ;this.w = w ;this.next = next ;}}Edge[] e = new Edge[M] ;int eid ;void add(int u , int v  , int  w){e[eid] = new Edge(v, w, head[u]) ;head[u] = eid++ ;}int[] inCnt = new int[N] ;int n ; int[] dist = new int[N] ;boolean[] inq = new boolean[N] ;final int inf = -1000000000 ;int spfa(){Arrays.fill(dist , inf) ;Arrays.fill(inq, false) ;Queue<Integer> q = new LinkedList<Integer>() ;q.add(0) ;dist[0] = 0 ;inq[0] = true ;while(! q.isEmpty()){int u = q.poll() ;inq[u] = 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 ;q.add(v) ;}}}}int reslut = Integer.MIN_VALUE ;for(int i = 1 ; i <= n ; i++){if(dist[i] != inf){reslut = Math.max(reslut, dist[i]) ;}}return reslut ; }void solve(){int t = in.nextInt() ;while(t-- > 0){n = in.nextInt() ;int m = in.nextInt() ;Arrays.fill(inCnt , 0) ;Arrays.fill(head, -1) ;eid = 0 ;for(int i = 1 ; i <= m ; i++){int u = in.nextInt() ;int v = in.nextInt() ;int w = in.nextInt() ;add(u, v, w) ;inCnt[v]++ ;}for(int i = 1 ; i <= n ; i++){if(inCnt[i] == 0){add(0, i, 0) ;}}out.println(spfa()) ;}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 int[] nextInts(int n) {    int[] nums = new int[n];    for (int i = 0; i < n; i++) {    nums[i] = nextInt();    }    return nums;    }    public long nextLong() {    return Long.parseLong(next());    }    public double nextDouble() {    return Double.parseDouble(next());    }    public BigInteger nextBigInteger() {    return new BigInteger(next());    }    }

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