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
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缩点后是一个DAG,然后就只求DAG最长路,可以直接spfa;至于酒吧的话就缩点的时候或一下即可
// MADE BY QT666
#include<cstdio>
#include<algorithm>
#include<vector>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=500050;
int gi()
{int x=0,flag=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') flag=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x*flag;
}
int head[N],nxt[N],to[N],v[N],zhan[N],fr[N],dfn[N],low[N],vis[N],tt,cnt,n,m,pd[N],check[N],tot,sum;
int S,P,w[N],dis[N],q[N*20],ans;
vector<int>p[N];
void tarjan(int x){dfn[x]=low[x]=++tt;zhan[++sum]=x;vis[x]=1;int y;for(int i=head[x];i;i=nxt[i]){y=to[i];if(!dfn[y]){tarjan(y);low[x]=min(low[x],low[y]);}else if(vis[y]) low[x]=min(low[x],dfn[y]);}if(low[x]==dfn[x]){tot++;do {y=zhan[sum--];vis[y]=0,w[tot]+=v[y];pd[tot]|=check[y],fr[y]=tot;for(int i=head[y];i;i=nxt[i]) p[tot].push_back(to[i]);} while(y!=x);}
}
void spfa(){q[0]=fr[S];dis[fr[S]]=w[fr[S]];int t=0,sum=1;while(t<sum){int now=q[t++];for(int i=0;i<p[now].size();i++){int y=fr[p[now][i]];if(y!=now&&dis[y]<dis[now]+w[y]){dis[y]=dis[now]+w[y];q[sum++]=y;}}}
}
void lnk(int x,int y){to[++cnt]=y,nxt[cnt]=head[x],head[x]=cnt;}
int main(){n=gi(),m=gi();for(int i=1;i<=m;i++){int x=gi(),y=gi();lnk(x,y);}for(int i=1;i<=n;i++) v[i]=gi();S=gi(),P=gi();for(int i=1;i<=P;i++){int x=gi();check[x]=1;}tarjan(S);spfa();for(int i=1;i<=tot;i++) if(pd[i]) ans=max(ans,dis[i]);printf("%d\n",ans);
}