Problem Description

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?ii-th path from the?Si?-th flag to the?Ti?-th flag has length?Li?.

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

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?0<N≤10000?and?0<M≤100000as described above.

Each of the following?M?lines contains three integers?Si?,?Ti?, and?Li??(0<Li?<1000)?describing a path in the ski resort.

Output

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

Sample?Input

1
5 4
1 3 3
2 3 4
3 4 1
3 5 2

???????Sample????????Output

6

題意：t 組數據，每組給出一個 n 個點 m 條邊的帶權有向圖，問整個圖的最長路

思路：DAG 圖求最長路，利用拓撲排序來解決即可

Source Program

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #include<bitset> #define EPS 1e-9 #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long #define Pair pair<int,int> const int MOD = 1E9+7; const int N = 50000+5; const int dx[] = {1,-1,0,0,-1,-1,1,1}; const int dy[] = {0,0,-1,1,-1,1,-1,1}; using namespace std;struct Node{int to,dis;Node(){}Node(int to,int dis):to(to),dis(dis){} }; vector<Node> G[N]; int in[N]; int dis[N]; int n,m;void topSort() {stack<int > S;for(int i=1; i<=n; i++)if(!in[i])S.push(i);while(!S.empty()) {int x=S.top();S.pop();for(int j=0; j<G[x].size(); j++) {int y=G[x][j].to;dis[y]=max(dis[y],dis[x]+G[x][j].dis);in[y]--;if(!in[y])S.push(y);}} }int main() {int T;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);memset(in,0,sizeof(in));memset(dis,0,sizeof(dis));for(int i=0; i<=n; i++)G[i].clear();for(int i=1; i<=m; i++) {int x,y,dis;scanf("%d%d%d",&x,&y,&dis);Node temp;temp.to=y;temp.dis=dis;in[y]++;G[x].push_back(temp);}topSort();int res=-INF;for(int i=1;i<=n;i++)res=max(res,dis[i]);printf("%d\n",res);}return 0; }

?

總結

以上是生活随笔為你收集整理的Skiing（2017 ACM-ICPC 亚洲区(乌鲁木齐赛区)网络赛 H）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。