20210812 数列,数对,最小距离,真相

int n;
LL a,b,c;

LL d,xx,yy,k1,k2,ans;

LL exgcd(LL a,LL b) {
	if( !b ) { xx = 1, yy = 0; return a; }
	LL d = exgcd(b,a%b);
	LL z = xx; xx = yy, yy = z - a / b * yy;
	return d;
}

signed main() {
//	freopen("a.in","r",stdin);
//	freopen("a.out","w",stdout);
	read(n,a,b);
	if( a > b ) swap(a,b);
	d = exgcd(a,b), k1 = b / d, k2 = a / d;
	For(i,1,n) {
		read(c); c = -c;
		if( c % d ) { puts("-1"); return 0; }
		LL x = (c/d*xx % k1+k1)%k1, y = (c-a*X)/b;
		if( abs(x-k1)+abs(y+k2) < abs(X)+abs(y) ) x -= k1, y += k2;
		ans += abs(X)+abs(y);
	}
	write(ans);
	return iocl();
}
/*
1 455 824
412
*/

const int n = 1e5+5;
int n;
struct Node { int a,b,w; } a[n];

int mx,lsh[N*2];
LL ans;

#define ls (u<<1)
#define rs (u<<1|1)
namespace seg {
struct Node { int l,r; LL mx,add; } t[N*8];
void up(int u) { t[u].mx = max(t[ls].mx,t[rs].mX); }
void down(int u,LL X) { t[u].mx += x, t[u].add += x; }
void down(int u) { down(ls,t[u].add), down(rs,t[u].add), t[u].add = 0; }
void build(int u,int l,int r) {
	t[u] = Node{l,r,0,0};
	if( l == r ) return;
	int mid = l+r>>1;
	build(ls,l,mid), build(rs,mid+1,r);
}
void modify(int u,int p,LL X) {
	if( t[u].l == t[u].r ) { ckmax(t[u].mx,X); return; }
	down(u);
	modify( p<=t[ls].r?ls:rs ,p,X);
	up(u);
}
void add(int u,int l,int r,LL X) {
	if( l <= t[u].l && t[u].r <= r ) { down(u,X); return; }
	down(u);
	if( l <= t[ls].r ) add(ls,l,r,X);
	if( t[rs].l <= r ) add(rs,l,r,X);
	up(u);
}
LL query(int u,int l,int r) {
	if( l <= t[u].l && t[u].r <= r ) return t[u].mx;
	down(u);
	LL res = 0;
	if( l <= t[ls].r ) res = query(ls,l,r);
	if( t[rs].l <= r ) ckmax(res,query(rs,l,r));
	return res;
}
}
#undef ls
#undef rs

signed main() {
	read(n);
	For(i,1,n) read(a[i].a,a[i].b,a[i].w), lsh[++mx] = a[i].a, lsh[++mx] = a[i].b;
	sort(lsh+1,lsh+mx+1), mx = unique(lsh+1,lsh+mx+1)-lsh-1;
	For(i,1,n) a[i].a = lower_bound(lsh+1,lsh+mx+1,a[i].a)-lsh,
			   a[i].b = lower_bound(lsh+1,lsh+mx+1,a[i].b)-lsh;
	sort(a+1,a+n+1,[](const Node &x,const Node &y){return x.a+x.b<y.a+y.b;});
	seg::build(1,1,mX);
	For(i,1,n) {
		seg::modify(1,a[i].a,seg::query(1,1,min(a[i].a,a[i].b))+a[i].w);
		if( a[i].a < a[i].b ) seg::add(1,a[i].a+1,a[i].b,a[i].w);
	}
	write(seg::t[1].mX);
	return iocl();
}

typedef pair<LL,int> PLI;
const int n = 2e5+5;
int n,m,p,id[n],mm=1,head[n],to[N*2],w[N*2],nxt[N*2];

PLI dis[n],dis2[n];
struct Node { int id; LL dis,dis2; };
bool operator < (const Node &x,const Node &y)
	{ return x.dis!=y.dis ? x.dis>y.dis : x.dis2>y.dis2; }
priority_queue<Node> pq;

signed main() {
//	freopen("c.in","r",stdin);
//	freopen("c.out","w",stdout);
	read(n,m,p);
	For(i,1,p) read(id[i]);
	For(i,1,m) {
		int x,y,z; read(x,y,z);
		to[++mm] = y, w[mm] = z, nxt[mm] = head[x], head[x] = mm;
		to[++mm] = x, w[mm] = z, nxt[mm] = head[y], head[y] = mm;
	}
	mem(dis,0x3f,n), mem(dis2,0x3f,n);
	For(i,1,p) dis[id[i]] = MP(0,id[i]), pq.push(Node{id[i],0,dis2[id[i]].fi});
	while( !pq.empty() ) {
		Node now = pq.top(); pq.pop();
		int u = now.id;
		if( dis[u].fi < now.dis || (dis[u].fi==now.dis && dis2[u].fi<now.dis2) )
			conTinue;
//		printf("@ %d %lld %lldn",u,dis[u].fi,dis2[u].fi);
		for(int i = head[u], v; v = to[i], i; i = nxt[i]) {
			bool flg = 0;
			if( dis[u].fi+w[i] < dis[v].fi ) {
				if( dis[u].se != dis[v].se ) dis2[v] = dis[v];
				dis[v].fi = dis[u].fi+w[i], dis[v].se = dis[u].se, flg = 1;
			} else if( dis[u].se != dis[v].se && dis[u].fi+w[i] < dis2[v].fi )
				dis2[v].fi = dis[u].fi+w[i], dis2[v].se = dis[u].se, flg = 1;
			else if( dis2[u].se != dis[v].se && dis2[u].fi+w[i] < dis2[v].fi )
				dis2[v].fi = dis2[u].fi+w[i], dis2[v].se = dis2[u].se, flg = 1;
			if( flg ) pq.push(Node{v,dis[v].fi,dis2[v].fi});
		}
	}
	For(i,1,p) write(dis2[id[i]].fi,' ');
	return iocl();
}