把点编号改成1-N，加一点0，从0点到之前任意入度为0的点之间连一条边权为0的边，求0点到所有点的最长路。
SPFA模板留底用
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <string>
#include <iostream>
#include <cmath>
#define ll long long
#define inf 1000000000
#define maxn 1010
using namespace std; struct Edge
{
int from,to;
int dist;
Edge(int a,int b,int c)
{
from=a,to=b,dist=c;
}
};
struct SPFA
{
int n,m;
vector<Edge> edges;
vector<int> g[maxn];
int d[maxn];
int p[maxn];
int cnt[maxn];
bool inq[maxn]; void init(int n_)
{
n=n_;
int i;
for(i=; i<=n; i++)
{
g[i].clear();
}
edges.clear();
} void addedge(int from,int to,double dist)
{
edges.push_back(Edge(from,to,dist));
m=edges.size();
g[from].push_back(m-);
} void spfa(int s)
{
int i;
queue<int> q;
memset(inq,,sizeof(inq));
memset(cnt,,sizeof(cnt));
for(i=; i<=n; i++)
{
d[i]=-inf;
}
d[s]=;
inq[s]=true;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
inq[u]=false;
for(i=; i<g[u].size(); i++)
{
Edge& e=edges[g[u][i]];
if(d[e.to]<d[u]+e.dist)
{
d[e.to]=d[u]+e.dist;
p[e.to]=g[u][i];
if(!inq[e.to])
{
q.push(e.to);
inq[e.to]=true;
}
}
}
}
int ans=;
for(i=;i<=n;i++)
{
ans=max(ans,d[i]);
}
printf("%d\n",ans+);
}
};
SPFA solver;
int N,M;
int ru[maxn]; int main()
{
// freopen("input.txt","r",stdin);
while ( scanf( "%d%d", &N, &M ) == )
{
memset( ru, , sizeof(ru) );
solver.init(N);
for ( int i = ; i < M; ++i )
{
int u, v, w;
scanf( "%d%d%d", &u, &v, &w );
u++,v++;
++ru[v];
solver.addedge(u, v, w );
}
for ( int i = ; i <= N; ++i )
{
if ( ru[i] == )
solver.addedge( , i, );
}
solver.spfa();
}
return ;
}