萌新87pts wa on #3#11
查看原帖
萌新87pts wa on #3#11
305925
Liu45318楼主2021/7/25 21:35

快调疯了,救救孩子吧

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5*1e5+10;

int n,m;
vector<int> vec[MAXN];
int s,p,arr[MAXN];
bool bar[MAXN];

void input(){
	cin>>n>>m;
	for (int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		vec[u].push_back(v);
	}
	for (int i=1;i<=n;i++)
		cin>>arr[i];
	cin>>s>>p;		
	for (int i=1;i<=p;i++){
		int t;
		cin>>t;
		bar[t]=true;
	}
}

stack<int> sta;
int tot,num,dfn[MAXN],low[MAXN],col[MAXN];

void tarjan(int u){
	dfn[u]=low[u]=++tot;
	sta.push(u);
	for (int i=0;i<vec[u].size();i++){
		int v=vec[u][i];
		if (!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else 
			if (!col[v])
				low[u]=min(low[u],low[v]);
	}
	if (dfn[u]==low[u]){
		col[u]=++num;
		while (sta.top()!=u){
			col[sta.top()]=num;
			sta.pop();
		}
		sta.pop();
	}
}

vector<int> g[MAXN];
int val[MAXN];
bool ending[MAXN];

void shrink(){
	for (int i=1;i<=n;i++)
		if (!dfn[i])
			tarjan(i);
	for (int u=1;u<=n;u++){
		val[col[u]]+=arr[u];
		if (bar[u]) ending[col[u]]=true;
		for (int i=0;i<vec[u].size();i++){
			int v=vec[u][i];
			if (col[u]!=col[v])
				g[col[u]].push_back(col[v]);
		}
	}
}

int dis[MAXN];
bool vis[MAXN];
struct Compare{
	bool operator ()(const int x,const int y)const{
		return dis[x]<dis[y];
	}
};
priority_queue<int,vector<int>,Compare> que;
int answer;

void dijkstra(){
	for (int i=1;i<=num;i++)
		dis[i]=val[i];
	que.push(col[s]);
	while (!que.empty()){
		int u=que.top();
		que.pop();
		if (vis[u]) continue;
		vis[u]=true; 
		for (int i=0;i<g[u].size();i++){
			int v=g[u][i];
			if (dis[u]+val[v]>dis[v]){
				dis[v]=dis[u]+val[v];
				que.push(v);
			}
		}
	}

}

void solve(){
	for (int i=1;i<=num;i++)
		if (ending[i]&&vis[i])
			answer=max(answer,dis[i]);	
}

void output(){
	cout<<answer<<endl;
}

int main(){
	input();
	shrink();
	dijkstra();
	solve();
	output();
	return 0;
}
2021/7/25 21:35
加载中...