题意：在这个寒假中，鲍勃有计划在山区度假胜地滑雪。这个滑雪胜地有M个不同的滑雪道和N个不同的标志位于那些转弯处点。从第S标记到第T标志的第i路径具有长度L。每个路径必须遵循降低高度的原则，起点必须严格高于终点。 现在，你应该帮助鲍勃找到最长的滑雪道。

思路：因为说起点必须严格高于终点，所以是一个有向图，而且不可能存在环，可以看作是一个DAG模型， 求DAG上的最长路可以用dp来求，有些时候也可以看作AOE网，这样就可以用拓扑排序来求关键路径来解决了；

代码：

 

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define MP make_pairconst int N = 100000 + 10;const int INF = 0x3f3f3f3f; vector
          
           
             > edge[N]; class Topological{private: int tot = 0, vis[N], n; queue
            
              Q;public: int in[N], dist[N], topo[N]; void Init(int n){ this -> n = n; for(int i = 1; i <= n; ++ i) vis[i] = 0, dist[i] = - INF; } bool Topo_Sort(){ //拓扑排序 for(int i = 1; i <= n; ++ i){ if(in[i] == 0){ Q.push( i ); vis[i] = true; dist[i] = 0; topo[tot++] = i; } } while(!Q.empty()){ int u = Q.front(); Q.pop(); for(int i = edge[u].size() - 1; i >= 0; -- i){ int v = edge[u][i].first; -- in[v]; if(in[v] == 0 && !vis[v]){ vis[v] = true; Q.push( v ); topo[tot++] = v; } } } return tot == n ? true : false; } int Get_Cpm(){ //求关键路径 for(int i = 0; i < tot; ++ i){ int u = topo[i]; for(int j = edge[u].size() - 1; j >= 0; -- j){ int v = edge[u][j].first; int c = edge[u][j].second; if(dist[v] < dist[u] + c) dist[v] = dist[u] + c; } } int ans = 0; for(int i = 1; i <= n; i++) if(dist[i] > ans) ans = dist[i]; return ans; }}Topo;void Input_data(int &n, int &m){ int u, v, c; scanf("%d %d", &n, &m); Topo.Init( n ); for(int i = 1; i <= m; ++ i){ scanf("%d %d %d", &u, &v, &c); edge[u].push_back(MP(v, c)); ++ Topo.in[v]; }}int main(){ int T, n, m; scanf("%d", &T); while(T --){ Input_data(n, m); Topo.Topo_Sort(); printf("%d\n", Topo.Get_Cpm()); for(int i = 1; i <= n; ++ i) edge[i].clear(); }}