传送门 Description Input 第一行包含两个整数N、M。N表示路口的个数，M表示道路条数。接下来M行，每行两个整数，这两个整数都在1到N之间，第i+1行的两个整数表示第i条道路的起点和终点的路口编号。接下来N行，每行一个整数，按顺序表示每个路口处的ATM机中的钱数。接下来一行包含两个整数S、P，S表示市中心的编号，也就是出发的路口。P表示酒吧数目。接下来的一行中有P个整数，表示P个有酒吧的路口的编号 Output 输出一个整数，表示Banditji从市中心开始到某个酒吧结束所能抢劫的最多的现金总数。 Sample Input 6 7 1 2 2 3 3 5 2 4 4 1 2 6 6 5 10 12 8 16 1 5 1 4 4 3 5 6 Sample Output 47 HINT 50%的输入保证N, M<=3000。所有的输入保证N, M<=500000。每个ATM机中可取的钱数为一个非负整数且不超过4000。输入数据保证你可以从市中心沿着Siruseri的单向的道路到达其中的至少一个酒吧。 Source
tarjan缩点+SPFA最长路 把这道题发上来主要是想说一下SPFA做这种最长路的时候的细节……
CODE：
#include<queue> #include<cstdio> using namespace std; const int N=5e5+10; struct edge { int nxt,to; }a[N],e[N]; int head[N],Head[N]; int dfn[N],low[N],size[N],block[N]; int s[N],top; int money[N],dis[N]; bool instack[N],b[N],bar[N]; int n,m,x,y,S,P,num,Num,tot,Time,ans; queue<int>q; inline int max(const int &a,const int &b){return a>b?a:b;} inline int min(const int &a,const int &b){return a<b?a:b;} inline void add(int x,int y) { a[++num].nxt=head[x],a[num].to=y,head[x]=num; } inline void add2(int x,int y) { e[++Num].nxt=Head[x],e[Num].to=y,Head[x]=Num; } void dfs(int now) { dfn[now]=low[now]=++Time; instack[now]=1; s[++top]=now; for(int i=head[now];i;i=a[i].nxt) if(!dfn[a[i].to]) { dfs(a[i].to); low[now]=min(low[now],low[a[i].to]); } else if(instack[a[i].to]) low[now]=min(low[now],dfn[a[i].to]); if(low[now]==dfn[now]) { tot++; int tmp; do tmp=s[top--],instack[tmp]=0,block[tmp]=tot,size[tot]+=money[tmp]; while(tmp!=now); } } inline void SPFA() { dis[block[S]]=size[block[S]]; q.push(block[S]); while(!q.empty()) { int tmp=q.front();q.pop(); b[tmp]=0; for(int i=Head[tmp];i;i=e[i].nxt) if(dis[e[i].to]<dis[tmp]+size[e[i].to]) { dis[e[i].to]=dis[tmp]+size[e[i].to]; if(!b[e[i].to]) b[e[i].to]=1,q.push(e[i].to); } } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%d%d",&x,&y),add(x,y); for(int i=1;i<=n;i++) scanf("%d",&money[i]); scanf("%d%d",&S,&P); for(int i=1;i<=P;i++) scanf("%d",&x),bar[x]=1; for(int i=1;i<=n;i++) if(!dfn[i]) dfs(i); for(int j=1;j<=n;j++) for(int i=head[j];i;i=a[i].nxt) if(block[j]!=block[a[i].to]) add2(block[j],block[a[i].to]); SPFA(); for(int i=1;i<=n;i++) if(bar[i]) ans=max(ans,dis[block[i]]); printf("%d",ans); return 0; }