记录编号	559285	评测结果	AWAWWWWWWW
题目名称	[SYOI 2019][東方S#]河童与灵力	最终得分	20
用户昵称	tat	是否通过	未通过
代码语言	C++	运行时间	0.781 s
提交时间	2021-02-27 11:35:19	内存使用	8.22 MiB

#include <bits/stdc++.h>
using namespace std; 
//第一问求强连通分量个数  第二问缩点后最短路  建陆方式 =》顺向花费0 逆向有花费 然后dj 
long long n,m,ed[50001][4],dfn[50001]={0},low[50001],t=0,ext[50001],num=0,bt[50001]={0};
vector<long long> ed1[50001];
stack<long long> stk;
//4,5,6行是求强连通分量 
struct edge{
	long long sp,cost;
};
vector<edge> ed2[50001];
struct dist{
	long long x,data;
	bool operator < (const dist &tmp)const{
		return this->data>tmp.data;
	}
	dist() :x(),data(){}
	dist(long long a,long long b): x(a),data(b){}
};
priority_queue<dist> dj; 
long long d[50001],st,v[50001],node[50001]={0},spell[50001]={0};
//8~21行是“缩点之后 ”求最短路  
void dfs(long long x){
	dfn[x]=low[x]=++t;
	ext[x]=1;
	stk.push(x);   //第一次访问时入栈 
	for(long long i=0;i<ed1[x].size();i++){
		long long to=ed1[x][i];
		if(!dfn[to]){
			dfs(to);
			low[x]=min(low[to],low[x]);
		}
		else if(ext[to]){
			//想想看：如果从y没有到x的路径，那么y早就应该出栈了 
			low[x]=min(low[x],dfn[to]);
		}
	}
	if(low[x]==dfn[x]){
		num++;
		long long y=0;
		do{
			y=stk.top();
			stk.pop();
			ext[y]=0;
			bt[y]=num;
			spell[num]+=node[y];
		}while(y!=x);
	} 
}
int main(int argc, char** argv) {
	freopen("EAST.in","r",stdin);
	freopen("EAST.out","w",stdout);
	cin>>n>>m>>st;
	for(long long i=1;i<=m;i++){
		cin>>ed[i][1]>>ed[i][2]>>ed[i][3];
		long long a=ed[i][1],b=ed[i][2];
		ed1[a].push_back(b);
	}
	for(long long i=1;i<=n;i++){
		cin>>node[i];
	}
	for(long long i=1;i<=n;i++){
		if(!dfn[i])dfs(i);
	}
	cout<<num<<endl;
	//问题1
	for(long long i=1;i<=m;i++){
		long long a=ed[i][1],b=ed[i][2],c=ed[i][3];
		if(bt[a]!=bt[b]){
			edge x,y;// x是正向边，y是逆向边 
			y.sp=a;
			x.sp=b;
			y.cost=c;
			x.cost=0;
			ed2[a].push_back(x);
			ed2[b].push_back(y);
		}
	} 
	//建新图
	memset(d,0x3f,sizeof(d)); 
	d[st]=0;
	dj.push(dist(st,0));
	while(!dj.empty()){
		long long z=dj.top().x,y=dj.top().data;
		dj.pop();
		if(v[z])continue;
		v[z]=1;
		for(long long i=0;i<ed2[z].size();i++){
			long long to=ed2[z][i].sp,c=ed2[z][i].cost;
			//cout<<to<<' '<<c<<' '<<d[to]<<endl;
			if(d[to]>d[z]+c){
				d[to]=d[z]+c;
				dj.push(dist(to,d[to]));
			}
		}
	}
	//dj
	long long ans=0;
	for(long long i=1;i<=num;i++){
		if(v[i]){
			ans-=d[i];
			ans+=spell[i];
			//cout<<spell[i]<<' '<<d[i]<<endl;
		}
	}
	cout<<ans;
	return 0;
}