#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;
}
不知哪里出了问题,烦请指导一下!