2021.08.24【NOIP提高A、B组】模拟 Party

思路：

正反边跑spfa

c o d e code code

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>

using namespace std;

int n, m, t;
int dis[10010], dis1[10010];
int head[10010], tot, head1[10010], tot1;
bool v[10010];
struct node
{
	int to, next, w;
}b[1001000], e[1001000];

void add(int x, int y, int w)
{
	b[++tot]=(node){y, head[x], w};
	head[x]=tot;
}

void add1(int x, int y, int w)
{
	e[++tot1]=(node){y, head1[x], w};
	head1[x]=tot1;
}

void spfa(int x)
{
	queue<int> q;
	memset(dis, 0x3f, sizeof(dis));
	dis[x]=0, v[x]=1;
	q.push(x);
	while(!q.empty())
	{
		int xx=q.front();
		q.pop();
		for(int i=head[xx]; i; i=b[i].next)
		{
			int y=b[i].to;
			if(dis[y]>dis[xx]+b[i].w)
			{
				dis[y]=dis[xx]+b[i].w;
				if(!v[y])
				{
					v[y]=1;
					q.push(y);
				}
			}
		}
		v[xx]=0;
	}
}

void spfa1(int x)
{
	queue<int> q;
	memset(dis1, 0x3f, sizeof(dis1));
	dis1[x]=0, v[x]=1;
	q.push(x);
	while(!q.empty())
	{
		int xx=q.front();
		q.pop();
		for(int i=head1[xx]; i; i=e[i].next)
		{
			int y=e[i].to;
			if(dis1[y]>dis1[xx]+e[i].w)
			{
				dis1[y]=dis1[xx]+e[i].w;
				if(!v[y])
				{
					v[y]=1;
					q.push(y);
				}
			}
		}
		v[xx]=0;
	}
}

int main()
{
	scanf("%d%d%d", &n, &m, &t);
	for(int i=1; i<=m; i++)
	{
		int x, y, w;
		scanf("%d%d%d", &x, &y, &w);
		add1(x, y, w);
		add(y, x, w); 
	}
	spfa(t);
	spfa1(t);
	int ans=-1e9;
	for(int i=1; i<=n; i++)
		if(dis[i]+dis1[i]>ans)
			ans=dis[i]+dis1[i];
	printf("%d", ans);
	return 0;
}