一、题目

Given the relations of all the activities of a project, you are supposed to find the earliest completion time of the project.

Input Specification:

Each input file contains one test case. Each case starts with a line containing two positive integers N (≤), the number of activity check points (hence it is assumed that the check points are numbered from 0 to N−1), and M, the number of activities. Then M lines follow, each gives the description of an activity. For the i-th activity, three non-negative numbers are given: S[i], E[i], and L[i], where S[i] is the index of the starting check point, E[i] of the ending check point, and L[i] the lasting time of the activity. The numbers in a line are separated by a space.

Output Specification:

For each test case, if the scheduling is possible, print in a line its earliest completion time; or simply output "Impossible".

Sample Input 1:9 120 1 60 2 40 3 51 4 12 4 13 5 25 4 04 6 94 7 75 7 46 8 27 8 4Sample Output 1:18Sample Input 2:4 50 1 10 2 22 1 31 3 43 2 5Sample Output 2:Impossible

二、思路

规规矩矩的拓扑排序

三、参考代码

#include 
      
        #include 
       
        #include 
        
         #define MaxVertexNum 102#define INFINITY 65536using namespace std;typedef int Vertex;         typedef int WeightType;        typedef int DataType;       int Indegree[MaxVertexNum];typedef struct ENode *Edge;struct ENode{    Vertex V1, V2;          WeightType Weight;  };typedef struct AdjVNode *PtrToAdjVNode; struct AdjVNode{    Vertex AdjV;           WeightType Weight;      PtrToAdjVNode Next;   }; typedef struct Vnode{    PtrToAdjVNode FirstEdge;    DataType Data;            } AdjList[MaxVertexNum];    /* AdjListÊÇÁÚ½Ó±íÀàÐÍ */  typedef struct GNode *LGraph;struct GNode{      int Nv;         int Ne;         AdjList G; };LGraph CreateGraph( int VertexNum );void InsertEdge( LGraph Graph, Edge E );LGraph BuildGraph();bool topSort(LGraph Graph);void find_max(LGraph Graph);int main() {    LGraph Graph = BuildGraph();        if( !topSort(Graph) ) printf("Impossible\n");    else {        find_max(Graph);    }    }LGraph CreateGraph( int VertexNum ){     Vertex V;    LGraph Graph;         Graph = (LGraph)malloc( sizeof(struct GNode) );     Graph->Nv = VertexNum;    Graph->Ne = 0;           for (V=0; V
         
          Nv; V++)        Graph->G[V].FirstEdge = NULL;                 return Graph; }      void InsertEdge( LGraph Graph, Edge E ){    PtrToAdjVNode newNode = new AdjVNode;    newNode->Weight = E->Weight;    newNode->AdjV = E->V2;        newNode->Next = Graph->G[E->V1].FirstEdge;    Graph->G[E->V1].FirstEdge = newNode;         }LGraph BuildGraph(){    LGraph Graph;    int Nv;    Edge E;    Vertex V;        scanf("%d", &Nv);    Graph = CreateGraph(Nv);        scanf("%d", &(Graph->Ne));        if(Graph->Ne) {        E = new ENode;        for(int i=0; i
          
           Ne; i++) {            scanf("%d %d %d", &(E->V1), &(E->V2), &(E->Weight));            InsertEdge(Graph, E);        }     }        for(V=0; V
           
            Nv; V++) { Graph->G[V].Data = 0; } return Graph; }bool topSort(LGraph Graph) { int cnt; Vertex V; queue
            
              Q; cnt = 0; for( V=0; V
             
              Nv; V++) Indegree[V] = 0; for( V = 0; V < Graph->Nv; V++) { for(PtrToAdjVNode W = Graph->G[V].FirstEdge; W; W=W->Next) { Indegree[W->AdjV]++; Graph->G[W->AdjV].Data = 0; } } for(V=0; V
              
               Nv; V++) if(Indegree[V] == 0) Q.push(V); while(!Q.empty()) { V = Q.front(); Q.pop(); cnt++; for(PtrToAdjVNode W = Graph->G[V].FirstEdge; W; W=W->Next) { if(--Indegree[W->AdjV] == 0) Q.push(W->AdjV); if(Graph->G[W->AdjV].Data < W->Weight + Graph->G[V].Data) Graph->G[W->AdjV].Data = W->Weight + Graph->G[V].Data; } } if(cnt != Graph->Nv) return false; return true; }void find_max(LGraph Graph){ Vertex V; int compTime; compTime = Graph->G[0].Data; for(V = 1; V < Graph->Nv; V++) { if(Graph->G[V].Data > compTime) compTime = Graph->G[V].Data; } printf("%d\n", compTime);}