把点编号改成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=0; 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-1); } void spfa(int s) { int i; queue<int> q; memset(inq,0,sizeof(inq)); memset(cnt,0,sizeof(cnt)); for(i=0; i<=n; i++) { d[i]=-inf; } d[s]=0; inq[s]=true; q.push(s); while(!q.empty()) { int u=q.front(); q.pop(); inq[u]=false; for(i=0; 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=0; for(i=1;i<=n;i++) { ans=max(ans,d[i]); } printf("%d ",ans+1); } }; SPFA solver; int N,M; int ru[maxn]; int main() { // freopen("input.txt","r",stdin); while ( scanf( "%d%d", &N, &M ) == 2 ) { memset( ru, 0, sizeof(ru) ); solver.init(N); for ( int i = 0; 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 = 1; i <= N; ++i ) { if ( ru[i] == 0 ) solver.addedge( 0, i, 0 ); } solver.spfa(0); } return 0; }