谨以此纪念终将逝去的TYVJ

TYVJ"/>

谨以此纪念终将逝去的TYVJ

TYVJ 1139向远方奔跑

希望TYVJ能跑的更远【当然也要跑的快，最好是比某记者还快

1139，曾经的缩点神题（现在的缩点模板题2333

缩点后点权SPFA最长路

170行一遍AC

【我好强

ACCode:

/*******************
Problem:TYVJ 1139 向远方奔跑 
Author:CXY1999
Status:Accepted
*******************/
//谨以此纪念即将逝去的TYVJ 
//希望TYVJ能走的更远
//向远方奔跑吧！2333 
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<set>
#include<algorithm>
#include<queue>
using namespace std;
#define maxn 3000+65
int n,m,Start;
vector<int> G[maxn];
vector<int> G2[maxn];
int D[maxn];
int D2[maxn];
bool END[maxn];
bool END2[maxn];
//建图相关 
int dfn[maxn];
int low[maxn];
int inS[maxn];
int st;
int Time;
int color[maxn];
int C;
struct Stack{int s[maxn+50];int ST;void push(int x){s[ST]=x;ST++;}void pop(){ST--;}int top(){return s[ST-1];}bool empty(){return ST==0;}void init(){ST=0;}Stack(){init();}
};
Stack S;
//tarjan相关 
int DIS[maxn];
queue<int> Q; 
//SPFA相关//Tarjan 
void SCC_tarjan(int x)
{dfn[x]=low[x]=Time;Time++;S.push(x);inS[x]=true;int buf=G[x].size();for(int i=0;i<buf;i++){int g=G[x][i];if(!dfn[g]){SCC_tarjan(g);low[x]=min(low[x],low[g]);}else if(inS[g]){low[x]=min(low[x],dfn[g]);}		}if(dfn[x]==low[x]){C++;do{x=S.top();S.pop();color[x]=C;inS[x]=false;}while(dfn[x]!=low[x]);}
}
void Tarjan()
{Time=1;for(int i=1;i<=n;i++){if(!dfn[i]){S.init();SCC_tarjan(i);}}
}
//初始化相关
void init()
{scanf("%d%d",&n,&m);for(int i=0;i<m;i++){int x,y;scanf("%d%d",&x,&y);G[x].push_back(y);}for(int i=1;i<=n;i++)scanf("%d",&D[i]);int R;scanf("%d%d",&Start,&R);for(int i=0;i<R;i++){int buf;scanf("%d",&buf);END[buf]=true;}
} 
//缩点相关 
void Shrink()
{for(int i=1;i<=n;i++){int buf=G[i].size();for(int j=0;j<buf;j++){int V=G[i][j];if(color[i]!=color[V])G2[color[i]].push_back(color[V]);//缩点 }END2[color[i]]|=END[i];D2[color[i]]+=D[i];}Start=color[Start]; 
} 
bool inQ[maxn];
//点权SPFA 
void SPFA(int S)
{memset(DIS,-1,sizeof(DIS));Q.push(S);inQ[S]=true;DIS[S]=D2[S];while(!Q.empty()){int x=Q.front();Q.pop();inQ[x]=false;int buf=G2[x].size();for(int i=0;i<buf;i++){int V=G2[x][i];if(DIS[x]+D2[V]>DIS[V]){DIS[V]=DIS[x]+D2[V];if(!inQ[V]){Q.push(V);inQ[V]=true;}}}}
}
void print_ans()
{int Ans=-1;for(int i=0;i<=C;i++)if(END2[i])Ans=max(Ans,DIS[i]);printf("%d\n",Ans);
}
int main()
{init();Tarjan();Shrink();SPFA(Start);print_ans();return 0;
}