SDUT - 2498: 数据结构实验之图论十一：AOE网上的关键路径

#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=50009, maxn=1e4+10;
structnode{
intu,v,w;
}es[maxm];
intn,m,d;
intin[maxn], out[maxn], dis[maxn], pre[maxn];
voidinit()
{
mem(pre,-1), mem(dis,0), mem(in,0), mem(out,0);
}
intrdijkstra()
{
intf;
for(inti=1;i<=n;i++) // n-1条边；最多需要(n-1)条边更新,所以i不能从2开始,要从1开始,多检测一次才知道是否有环    {
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;
pre[es[j].v]=es[j].u; // 类似 pre[i]=s; 记录前驱            }
elseif(dis[es[j].u]+es[j].w==dis[es[j].v] &&es[j].u<pre[es[j].v])
f=1, pre[es[j].v]=es[j].u;
        }
if(!f) return1;
    }
return0; // 在(i==n)最后一次如果还可以执行到这说明当中有环}
intmain()
{
intu,v,w,s;
while(~scanf("%d%d",&n,&m))
    {
init();
for(inti=0;i<m;i++)
        {
scanf("%d%d%d",&u,&v,&w);
es[i].u=v, es[i].v=u, es[i].w=w;
in[u]++, out[v]++;
        }
for(inti=1;i<=n;i++)
        {
if(in[i]==0) s=i;
if(out[i]==0) d=i;
        }
if(rdijkstra())
        {
printf("%d\n",dis[d]);
inth=d;
while(h!=-1&&pre[h]!=-1)
            {
printf("%d %d\n",h,pre[h]);
h=pre[h];
            }
        }
elseputs("-1");
    }
return0;
}