PTA 08-图8 How Long Does It Take 测试点3不过


#include <stdio.h>
#define Vertex int
#define Max 101
#define Cost int
#define INF 10000

struct GNode
{
    int nv;
    int ne;
    Cost G[Max][Max];
}mygraph;

int InCnt[Max] = {0};
int Earliest[Max] = {0};

void BuildGraph(int Nv, int Ne);
void Judge();

int main()
{
    int Nv, Ne;
    scanf("%d %d", &Nv, &Ne);
    BuildGraph(Nv, Ne);
    Judge();
    return 0;
}

void BuildGraph(int Nv, int Ne)  //建图
{
    for (int i = 0; i < Nv; i++)
    {
        for (int j = 0; j < Nv; j++)
        {
            mygraph.G[i][j] = INF;
        }
    }
    mygraph.nv = Nv;
    mygraph.ne = Ne;
    Vertex v1, v2;
    Cost tmpcost;
    for (int i = 0; i < Ne; i++)
    {
        scanf("%d %d %d", &v1, &v2, &tmpcost);
        InCnt[v2]++; //记录入度
        mygraph.G[v1][v2] = tmpcost;
    }
    return;
}

void Judge()
{
    Vertex now;
    int flag[mygraph.nv];
    for (int i = 0; i < mygraph.nv; i++)
    {
        flag[i] = 0;
    }
    Cost tmp;
    int cnt = mygraph.nv;
    int flag2 = 1;
    while (cnt && flag2)
    {
        flag2 = 0;
        for (int i = 0; i < mygraph.nv; i++) //将入度为0选出
        {
            if (!InCnt[i] && !flag[i])
            {
                flag[i] = 1;
                now = i;
                cnt--;
                flag2 = 1;  //如果有环,将不进while循环
                break;
            }
        }
        for (int i = 0; i < mygraph.nv; i++)
        {
            if (mygraph.G[now][i] != INF)
            {
                InCnt[i]--;
                tmp = Earliest[now] + mygraph.G[now][i];
                if (tmp > Earliest[i])
                {
                    Earliest[i] = tmp;
                }
            }
        }
    }
    if (cnt)
    {
        printf("Impossible");
    }
    else
    {
        tmp = 0;
        for (int i = 0; i < mygraph.nv; i++)
        {
            if (Earliest[i] > tmp)
            {
                tmp = Earliest[i];
            }
        }
        printf("%d", tmp);
    }
    return;
}

不知哪里出了问题,烦请指导一下!

img

img

img

img