题目链接：https://www.luogu.com.cn/problem/P1807
因为并没有保证1点的入度没有保证为0，所以先将所有的点的dis为0xc0，然后dis[1]=0，dis[n]=-INF。将所有连向1的点的w都设为-100001，这样拓扑到1这个节点时，dis就会被更新为0，然后接着往后找n。
AC代码：
1 #include<cstdio> 2 #include<iostream> 3 #include<queue> 4 #include<cstring> 5 using namespace std; 6 const int N=50005; 7 const int INF=-2147483646; 8 queue<int> q; 9 int n,m,tot; 10 struct node{ 11 int to,next,w; 12 }edge[N]; 13 int head[N],in[N],dis[N]; 14 void add(int u,int v,int w){ 15 edge[tot].to=v; 16 edge[tot].next=head[u]; 17 edge[tot].w=w; 18 head[u]=tot++; 19 } 20 void toposort(){ 21 for(int i=1;i<=n;i++) if(!in[i]) q.push(i); 22 while(!q.empty()){ 23 int u=q.front(); q.pop(); 24 for(int i=head[u];i!=-1;i=edge[i].next){ 25 int v=edge[i].to; 26 in[v]--; 27 dis[v]=max(dis[v],dis[u]+edge[i].w); 28 if(!in[v]) q.push(v); 29 } 30 } 31 } 32 int main(){ 33 memset(head,-1,sizeof(head)); 34 scanf("%d%d",&n,&m); 35 memset(dis,0xc0,sizeof(dis)); 36 dis[1]=0; dis[n]=INF; 37 if(m==0){ 38 printf("-1"); 39 return 0; 40 } 41 for(int i=1;i<=m;i++){ 42 int u,v,w; 43 scanf("%d%d%d",&u,&v,&w); 44 in[v]++; 45 if(v==1) add(u,v,-100001); 46 else add(u,v,w); 47 } 48 toposort(); 49 if(dis[n]==INF) { printf("-1"); return 0;} 50 printf("%d",dis[n]); 51 return 0; 52 }