HDU 4109 Instrction Arrangement

题意：给你一些机器指令，某些有先后顺序（若A->B,C->B则必须A、C执行完才能执行B），且有安全距离（若A->B 距离n）那么必须在从A执行算起n时间，才能执行B，一次可以运行多个指令，指令的完成只花费1,最后求执行完所有指令所需的最短的时间。

思想：① 求所有入度为0的点的“最短路”，这里的最短路其实是求最长路（dist[N]->0;dist[v]+map[v][u]>dist[u]）!!!

        ② 求出拓扑序列，计算出所有序列的最大值（这里就是最后一个执行玩的时间，最大时间）

///WA 没过 错误的
///改改AC了！我都不敢相信!!O__O"…
///我怎么感觉好像有漏洞一样啊，但是却过了!!什么情况?
 
#include <stdio.h>
#include <string.h>

#define N 1002
#define M 10000
#define MAXTIME 0
#define MOVE(x) (x=(x+1)%N)

int nodev[N];
int nodeu[M],data[M],next[M];
bool indegree[N];
bool outdegree[N];
int stack[N],top;

void Build_Graph(int m)
{
    int i,v,u,value,ind;
    
    memset(nodev,-1,sizeof(nodev)); ind=0;        
    memset(indegree,false,sizeof(indegree));
    memset(outdegree,false,sizeof(outdegree));
    
    for(i=1;i<=m;i++)
    {
        scanf("%d %d %d",&v,&u,&value);
        indegree[u]=true; outdegree[v]=true;
        ind++;
        next[ind]=nodev[v];
        nodeu[ind]=u;
        data[ind]=value;
        nodev[v]=ind;
    }
    
}

void getStack(int n)
{
    int i;
    for(top=i=0;i<n;i++)
    {
        if(!indegree[i] && outdegree[i])
            stack[top++]=i;
    }
}

int queue[N];
bool flag[N];
int time[N];
int start,mintime;
void SPFA(int s,int n)
{
    int i,v,u,value,front,rear;
    
    for(i=1;i<=n;i++)    time[i]=MAXTIME;
    front=-1; rear=-1; time[s]=0;
    memset(flag,false,sizeof(flag));
    for(i=nodev[s];i!=-1;i=next[i])
    {
        u=nodeu[i]; value=data[i];
        time[u]=value;
        queue[MOVE(rear)]=u;
        flag[u]=true;
    }
    
    while(front!=rear)
    {
        v=queue[MOVE(front)];
        flag[v]=false;
        for(i=nodev[v];i!=-1;i=next[i])
        {
            u=nodeu[i]; value=data[i];
            if(time[v]+value>time[u])
            {
                time[u]=time[v]+value;
                if(!flag[u])
                {
                    queue[MOVE(rear)]=u;
                    flag[u]=true;
                }
            }
        }
    }

}
int solve(int n)
{
    int i,k,v,temp;
    
    getStack(n); mintime=MAXTIME;
    for(k=0;k<top;k++)
    {
        v=stack[k];
        SPFA(v,n);

        for(temp=i=0;i<n;i++)
        {
            if(time[i]>temp)
                temp=time[i];
        }
        if(temp>mintime)
        {
            mintime=temp;
        }
    }
    return mintime+1;
}

int main()
{
    int n,m;
//    freopen("input.txt","r",stdin);
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        
        Build_Graph(m);
        printf("%d\n",solve(n));

    }
    
    return 0;
}