Data Structures and Algorithms (English) - 7-12 How Long Does It Take（25 分）

#include<bits/stdc++.h>#include<cmath>#define mem(a,b) memset(a,b,sizeof a)#define ssclr(ss) ss.clear(), ss.str("")#define INF 0x3f3f3f3f#define MOD 1000000007usingnamespacestd;
typedeflonglongll;
constintmaxm=10010;
structedge{
intu,v,w;
}es[maxm];
intn,m;
intdis[maxm], out[maxm];
voidinit()
{
mem(dis,0), mem(out,0);
}
intrdijkstra()
{
intf;
for(inti=1;i<=n;i++)
    {
f=0;
for(intj=0;j<m;j++)
if(dis[es[j].u]+es[j].w>dis[es[j].v])
f=1, dis[es[j].v]=dis[es[j].u]+es[j].w;
if(!f) return1;
    }
return0;
}
intmain()
{
init();
scanf("%d%d",&n,&m);
for(inti=0;i<m;i++)
    {
scanf("%d%d%d",&es[i].u,&es[i].v,&es[i].w);
out[es[i].u]++;
    }
vector<int>vd; // 最后一个测试点：存在多个出路for(inti=0;i<n;i++)
if(!out[i]) vd.push_back(i);
if(rdijkstra())
    {
intrs=-1;
for(inti=0;i<vd.size();i++)
rs=max(rs,dis[vd[i]]);
printf("%d\n",rs);
    }
elseputs("Impossible");
return0;
}