06-图7. How Long Does It Take (25).zip

#include <iostream> #include <queue> using namespace std; /* run this program using the console pauser or add your own getch, system("pause") or input loop */ #define MAX 110 #define INF 10000 #define max(a,b) (a)>(b)?(a):(b) int N=0,M=0; int cost[MAX][MAX]; int Earlist[MAX],indegree[MAX],outdegree[MAX]; void Creat() { cin>>N>>M; for(int i=0; i<N; i++) { for(int j=0; j<N; j++) { cost[i][j]=-1; } Earlist[i]=0; indegree[i]=0; outdegree[i]=0; } for(int i=0; i<M; i++) { int v1,v2,c; cin>>v1>>v2>>c; cost[v1][v2]=c;//v1<v2!! outdegree[v1]++; indegree[v2]++; } } int Ear() { queue<int> q; int i=0,front=0; for(i=0; i<N; i++) { if(indegree[i]==0) { q.push(i); indegree[i]--; } } int cnt=0; while(!q.empty()) { front=q.front();q.pop(); cnt++; for(i=0; i<N; i++) { if(cost[front][i] >=0) { indegree[i]--; Earlist[i]=max(Earlist[i],Earlist[front]+cost[front][i]); } } for(i=0; i<N; i++) { if(indegree[i] == 0) { q.push(i); indegree[i]--; } } } if(cnt==N) { return Earlist[front]; } return -1; } int main(int argc, char** argv) { int res=0; Creat(); if(Ear()==-1) { cout<<"Impossible"<<endl; } else { for(int i=0; i<N; i++) { if(outdegree[i] == 0) { res=max(res,Earlist[i]); } } cout<<res<<endl; } return 0; }