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

#include <bits/stdc++.h>
using namespace std; 
//第一问求强连通分量个数  第二问缩点后最短路  建陆方式 =》顺向花费0 逆向有花费 然后dj 
int n,m,ed[50001][4],dfn[50001]={0},low[50001],t=0,ext[50001],num=0,bt[50001]={0};
vector<int> ed1[50001];
stack<int> stk;
//4,5,6行是求强连通分量 
struct edge{
	int sp,cost;
};
vector<edge> ed2[50001];
struct dist{
	int x,data;
	bool operator < (const dist &tmp)const{
		return this->data<tmp.data;
	}
	dist() :x(),data(){}
	dist(int a,int b): x(a),data(b){}
};
priority_queue<dist> dj; 
int d[50001],st,v[50001],node[50001]={0},spell[50001]={0};
//8~21行是“缩点之后 ”求最短路  
void dfs(int x){
	dfn[x]=low[x]=++t;
	ext[x]=1;
	stk.push(x);   //第一次访问时入栈 
	for(int i=0;i<ed1[x].size();i++){
		int 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++;
		int 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(int i=1;i<=m;i++){
		cin>>ed[i][1]>>ed[i][2]>>ed[i][3];
		int a=ed[i][1],b=ed[i][2];
		ed1[a].push_back(b);
	}
	for(int i=1;i<=n;i++){
		cin>>node[i];
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i])dfs(i);
	}
	cout<<num<<endl;
	//问题1
	for(int i=1;i<=m;i++){
		int 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);
		}
	} 
	//建新图
	int maxx=1919810*(114+514);
	memset(d,1919810,sizeof(d)); 
	d[st]=0;
	v[st]=1;
	dj.push(dist(st,0));
	while(!dj.empty()){
		int x=dj.top().x,y=dj.top().data;
		dj.pop();
		for(int i=0;i<ed2[x].size();i++){
			int to=ed2[x][i].sp,c=ed2[x][i].cost;
			//cout<<to<<' '<<c<<' '<<d[to]<<endl;
			if(d[to]>d[x]+c){
				d[to]=d[x]+c;
				if(!v[to]){
					v[to]=1;
					dj.push(dist(to,d[to]));
				}
			}
		}
	}
	//dj
	int ans=0;
	for(int i=1;i<=num;i++){
		if(v[i]){
			ans+=spell[i];
			ans-=d[i];
			//cout<<spell[i]<<' '<<d[i]<<endl;
		}
	}
	cout<<ans;
	return 0;
}