首页 > 其他分享 >P2149 [SDOI2009] Elaxia的路线 题解

P2149 [SDOI2009] Elaxia的路线 题解

时间:2022-10-06 09:12:30浏览次数:59  
标签:opt int 题解 Read Edge SDOI2009 now Elaxia dis

首先考虑分别求出在两个人最短路上的边,这个就是用 \(s\) 跑一遍最短路,\(t\) 跑一遍最短路,然后枚举边 \((u,v)\),如果满足 \((s\to u) + (u\to v)+(t\to v)=(s\to t)\) 那么说明有向边 \(u\to v\) 就是一条在最短路上的有向边。

处理后,注意到我们得到了两张 DAG,然后题意有点坑,实际上只要路径重合都算一起走,无论相反还是相遇,问题在于两个人不可能一会相反一会相遇,因此考虑在第一个人的 DAG 上做两次记忆化搜索,一次只允许相遇边,一次只允许相反边。

Code:

/*
========= Plozia =========
	Author:Plozia
	Problem:P2149 [SDOI2009] Elaxia的路线
	Date:2022/10/5
========= Plozia =========
*/

#include <bits/stdc++.h>
typedef long long LL;
using std::queue;
using std::priority_queue;

const int MAXN = 1500 + 5, MAXM = 3e5 + 5;
int n, m, s1, t1, s2, t2, Head[MAXN], cntEdge = 1;
LL dis[2][2][MAXN], f[MAXN][2];
bool book[MAXN], vis1[MAXM << 1], vis2[MAXM << 1];
struct node { int To; LL val; int Next; } Edge[MAXM << 1];
struct pri { int x; LL dis; bool operator <(const pri &fir)const { return dis > fir.dis; } } ;

int Read()
{
	int sum = 0, fh = 1; char ch = getchar();
	for (; ch < '0' || ch > '9'; ch = getchar()) fh -= (ch == '-') << 1;
	for (; ch >= '0' && ch <= '9'; ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch ^ 48);
	return sum * fh;
}
void add(int x, int y, int z) { ++cntEdge; Edge[cntEdge] = (node){y, z, Head[x]}; Head[x] = cntEdge; }
LL Min(LL fir, LL sec) { return (fir < sec) ? fir : sec; }
LL Max(LL fir, LL sec) { return (fir > sec) ? fir : sec; }

void Dijkstra(int s, int who, int opt)
{
	for (int i = 1; i <= n; ++i) book[i] = 0;
	priority_queue <pri> q; q.push((pri){s, 0}); dis[who][opt][s] = 0;
	while (!q.empty())
	{
		int x = q.top().x; q.pop(); if (book[x]) continue ; book[x] = 1;
		for (int i = Head[x]; i; i = Edge[i].Next)
		{
			int u = Edge[i].To; if (book[u]) continue ;
			if (dis[who][opt][u] > dis[who][opt][x] + Edge[i].val)
			{
				dis[who][opt][u] = dis[who][opt][x] + Edge[i].val;
				q.push((pri){u, dis[who][opt][u]});
			}
		}
	}
}

LL dfs(int now, int opt)
{
	if (f[now][opt] != -1) return f[now][opt]; f[now][opt] = 0;
	for (int i = Head[now]; i; i = Edge[i].Next)
	{
		int u = Edge[i].To; if (book[u] || !vis1[i]) continue ;
		book[u] = 1; LL s = dfs(u, opt);
		f[now][opt] = Max(f[now][opt], s + vis2[i ^ opt] * Edge[i].val); book[u] = 0;
	}
	return f[now][opt];
}

int main()
{
	n = Read(), m = Read(); s1 = Read(), t1 = Read(), s2 = Read(), t2 = Read();
	memset(dis, 0x3f, sizeof(dis));
	for (int i = 1; i <= m; ++i) { int x = Read(), y = Read(), z = Read(); add(x, y, z); add(y, x, z); }
	Dijkstra(s1, 0, 0); Dijkstra(t1, 0, 1); Dijkstra(s2, 1, 0); Dijkstra(t2, 1, 1);
	for (int i = 2; i <= cntEdge; i += 2)
	{
		int x = Edge[i].To, y = Edge[i ^ 1].To;
		if (dis[0][0][x] + Edge[i].val + dis[0][1][y] == dis[0][0][t1]) vis1[i ^ 1] = 1;
		if (dis[0][1][x] + Edge[i].val + dis[0][0][y] == dis[0][0][t1]) vis1[i] = 1;
		if (dis[1][0][x] + Edge[i].val + dis[1][1][y] == dis[1][0][t2]) vis2[i ^ 1] = 1;
		if (dis[1][1][x] + Edge[i].val + dis[1][0][y] == dis[1][0][t2]) vis2[i] = 1;
	}
	for (int i = 1; i <= n; ++i) book[i] = 0;
	memset(f, -1, sizeof(f)); book[s1] = 1; f[t1][0] = f[t1][1] = 0;
	f[s1][0] = dfs(s1, 0), f[s1][1] = dfs(s1, 1);
	LL ans = -1; for (int i = 1; i <= n; ++i) ans = Max(ans, Max(f[i][0], f[i][1])); printf("%lld\n", ans); return 0;
}

标签:opt,int,题解,Read,Edge,SDOI2009,now,Elaxia,dis
From: https://www.cnblogs.com/Plozia/p/16756999.html

相关文章

  • 第一道面试题 第一道困难题解答记录
    输入一个奇数n,输出一个由*构成的n阶实心菱形。输入格式一个奇数n。输出格式输出一个由*构成的n阶实心菱形。具体格式参照输出样例。数据范围1≤n≤99输......
  • 【题解】「AGC013D」Piling Up
    传送门题目大意:开始有\(n\)个黑白球在袋子中,但是不知道具体多少黑球白球,有\(m\)次操作,每次从袋子中先拿一个球,再放入一个黑球一个白球,再拿走一个球,求所有初始情况下......
  • 【whk】三调生物-缝合小鼠实验——小鼠肥胖原因 题解
    今天生物考试考了个小鼠肥胖原因的题,写个题解((我根据一位不愿意透露姓名的刘佳兴的描述扒下来了一道似乎很类似的题\((1)\)首先开第一问。他给定了限制是两种原因之一,......
  • CF1739 部分题解
    比赛链接:https://codeforces.com/contest/1739AB水题//bySkyRainWind#include<cstdio>#include<vector>#include<cstring>#include<iostream>#include<algo......
  • CF1707B题解
    原题CF1707BDifferenceArray思路概述题意分析给定一个长度为\(n\)的序列\(\{a\}\)。每次执行以下操作对序列\(\{a\}\)进行差分,得到差分序列\(b_i=a_{i+1}-a......
  • 题解【CF1149C Tree Generator】
    CF1149CTreeGenerator™不一定更好的阅读体验。牛逼题&ZROIDay3数据结构选讲。来一波详细的题解。当时和\(\texttt{ys}\),\(\texttt{hy}\)还有小猴子讨论了半......
  • [题解]洛谷 P4700
    经典题没做出来,是不是该死?是不是该死?首先缩点什么的都是套路性的,然后发现一个事,你要是缩完点直接做,就相当于有向无玕图上标记一些点,求另一些点能到达多少个标记点,这个似乎......
  • CSP-S 模拟赛 #2 题解
    300rk3。题面是本校OJ的,链接挂了找我。upd:T1被xiaopanda的hack数据卡了。T1-A-BProblem出题是一件痛苦的事情!题目看多了也有审美疲劳,于是我舍弃了大家所熟......
  • texlive编译中发现字体有问题解决
    这里可以用tlmgrinfo命令搜索需要下载的字体并从CTAN官网下载。一般这个时候也会有对应的路径,比如texmf-dist/fonts/。把下载的字体解压放在这些路径下,然后分别运行mktexl......
  • 【LGR-122】T1 & T2 题解
    T1下面所说的做法来自于dty(%%%%%%%%%)注意到每一个数的绝对值是大于等于\(2\)的,那么就可以发现一个性质:当一个区间长度为\(len\)时,如果\(len\ge62\),那么这个区间的......