用户名  找回密码
 中文实名注册
查看: 339|回复: 2

P1073

[复制链接]

12

主题

9

回帖

1540

积分

版主

积分
1540
发表于 2024-5-19 16:12:59 | 显示全部楼层 |阅读模式
[C++] 纯文本查看 复制代码
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int n,m,cnt,h1[900001],h2[900001],mid,f1[900001],f2[900001],ans=-0x3f3f3f3f;
int j[900001];
bool b[900001];
struct edge{
	int n,t;
}a1[900001],a2[900001];
void add1(int f,int t)
{
	a1[++cnt].t=t;
	a1[cnt].n=h1[f];
	h1[f]=cnt;
}
void add2(int f,int t)
{
	a2[++cnt].t=t;
	a2[cnt].n=h2[f];
	h2[f]=cnt;
}
void spfa1(int s) 
{
	queue<int> q;
	memset(f1,0x3f,sizeof f1);
	memset(b,0,sizeof b);
	b[s]=1;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();b[u]=0;
		f1[u]=min(f1[u],j[u]);
		for(int i=h1[u];i;i=a1[i].n)
		{
			int to=a1[i].t;
			if(f1[to]>f1[u])
			{
				f1[to]=f1[u];
				if(!b[to]) b[to]=1,q.push(to);
			}
		}
	}
}
void spfa2(int s) 
{
	queue<int> q;
	memset(b,0,sizeof b);
	b[s]=1;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();b[u]=0;
		f2[u]=max(f2[u],j[u]);
		for(int i=h2[u];i;i=a2[i].n)
		{
			int to=a2[i].t;
			if(f2[to]<f2[u])
			{
				f2[to]=f2[u];
				if(!b[to]) b[to]=1,q.push(to);
			}
		}
	}
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>j[i];
    for(int i=1;i<=m;i++)
	{
		int x,y,w;
		cin>>x>>y>>w;
		add1(x,y),add2(y,x);
		if(w==2) add1(y,x),add2(x,y);
	}
	spfa1(1);
	spfa2(n);
	for(int i=1;i<=n;i++) ans=max(ans,f2[i]-f1[i]);
	cout<<ans;
    return 0;
}
回复

举报

7

主题

121

回帖

2217

积分

金牌会员

积分
2217
发表于 2024-6-9 18:56:05 | 显示全部楼层
hello.zip (894 Bytes, 下载次数: 9)
回复

举报

7

主题

121

回帖

2217

积分

金牌会员

积分
2217
发表于 2024-6-9 19:25:20 | 显示全部楼层
2222.zip (637.4 KB, 下载次数: 6)
回复

举报

您需要登录后才可以回帖 登录 | 中文实名注册

本版积分规则

手机版|小黑屋|东台市机器人学会;盐城市极创科技有限公司 ( 苏ICP备2021035350号-1;苏ICP备2021035350号-2;苏ICP备2021035350号-3 )

GMT+8, 2025-4-13 17:16 , Processed in 0.118146 second(s), 30 queries .

Powered by Discuz! X3.5

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表