思路，求图中最长路，一开始想着直接跑spfa，之后发现环不会处理，那就先tarjan缩点，之后spfa就好了。
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<stack> 5 #include<queue> 6 using namespace std; 7 const int N=500005; 8 int n,m,cnt,dcnt,tim,s,ans,x[N],y[N],hd[N],val[N],vl[N],bar[N],dfn[N],low[N],belong[N],dis[N]; 9 bool instk[N],b[N]; 10 stack<int>stk; 11 queue<int>q; 12 struct edge 13 { 14 int to,nxt; 15 }v[N]; 16 void addedge(int x,int y) 17 { 18 v[++cnt].nxt=hd[x]; 19 v[cnt].to=y; 20 hd[x]=cnt; 21 } 22 void tarjan(int u) 23 { 24 dfn[u]=low[u]=++tim; 25 stk.push(u); 26 instk[u]=1; 27 for(int i=hd[u];i;i=v[i].nxt) 28 if(!dfn[v[i].to]) 29 { 30 tarjan(v[i].to); 31 low[u]=min(low[u],low[v[i].to]); 32 } 33 else if(instk[v[i].to]) 34 low[u]=min(low[u],dfn[v[i].to]); 35 if(low[u]==dfn[u]) 36 { 37 ++dcnt; 38 while(1) 39 { 40 int t=stk.top(); 41 stk.pop(); 42 instk[t]=0; 43 belong[t]=dcnt; 44 vl[dcnt]+=val[t]; 45 if(t==u) 46 break; 47 } 48 } 49 } 50 int main() 51 { 52 scanf("%d%d",&n,&m); 53 for(int i=1;i<=m;i++) 54 { 55 scanf("%d%d",&x[i],&y[i]); 56 addedge(x[i],y[i]); 57 } 58 for(int i=1;i<=n;i++) 59 scanf("%d",val+i); 60 scanf("%d%d",&s,bar); 61 for(int i=1;i<=bar[0];i++) 62 scanf("%d",bar+i); 63 for(int i=1;i<=n;i++) 64 if(!dfn[i]) 65 tarjan(i); 66 cnt=0; 67 memset(hd,0,sizeof(hd)); 68 memset(v,0,sizeof(v)); 69 for(int i=1;i<=m;i++) 70 if(belong[x[i]]!=belong[y[i]]) 71 addedge(belong[x[i]],belong[y[i]]); 72 dis[belong[s]]=vl[belong[s]]; 73 b[belong[s]]=1; 74 q.push(belong[s]); 75 while(!q.empty()) 76 { 77 int u=q.front(); 78 q.pop(); 79 b[u]=0; 80 for(int i=hd[u];i;i=v[i].nxt) 81 if(dis[v[i].to]<dis[u]+vl[v[i].to]) 82 { 83 dis[v[i].to]=dis[u]+vl[v[i].to]; 84 if(!b[v[i].to]) 85 { 86 q.push(v[i].to); 87 b[v[i].to]=1; 88 } 89 } 90 } 91 for(int i=1;i<=bar[0];i++) 92 ans=max(ans,dis[belong[bar[i]]]); 93 printf("%d ",ans); 94 return 0; 95 }