【图论经典题目讲解】洛谷 P2149 Elaxia的路线

这篇具有很好参考价值的文章主要介绍了【图论经典题目讲解】洛谷 P2149 Elaxia的路线。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

P2149 Elaxia的路线

D e s c r i p t i o n \mathrm{Description} Description

给定 n n n 个点, m m m 条边的无向图,求 2 2 2 个点对间最短路的最长公共路径

S o l u t i o n \mathrm{Solution} Solution

最短路有可能不唯一,所以公共路径的长度就有可能不同。

2 2 2 条最短路都会经过的边(包括同向和异向)记录出来,并建立 1 1 1 个新图,那么由于最短路(可以看做一条链)一定不会走环,故新图必定是一个 有向无环图 (简称 D A G \mathrm{DAG} DAG),而 D A G \mathrm{DAG} DAG 图上就可以跑 DP 来求解最长链,由于找出的是 2 2 2 条最短路都经过的边,所以最长链其实就是 2 2 2 条最短路的最长公共路径。

故,该问题得以解决。文章来源地址https://www.toymoban.com/news/detail-829258.html

C o d e Code Code

#include <bits/stdc++.h>
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int SIZE = 1e6 + 10;

int N, M;
int X1, Y1, X2, Y2;
int h[SIZE], hs[SIZE], e[SIZE], ne[SIZE], w[SIZE], idx;
int D[4][SIZE], Vis[SIZE], in[SIZE], q[SIZE], hh, tt = -1;
int F[SIZE];

void add(int h[], int a, int b, int c)
{
	e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}

void Dijkstra(int Start, int dist[])
{
	for (int i = 1; i <= N; i ++)
		dist[i] = 1e18, Vis[i] = 0;
	priority_queue<PII, vector<PII>, greater<PII>> Heap;
	Heap.push({0, Start}), dist[Start] = 0;

	while (Heap.size())
	{
		auto Tmp = Heap.top();
		Heap.pop();

		int u = Tmp.second;
		if (Vis[u]) continue;
		Vis[u] = 1;

		for (int i = h[u]; ~i; i = ne[i])
		{
			int j = e[i];
			if (dist[j] > dist[u] + w[i])
			{
				dist[j] = dist[u] + w[i];
				Heap.push({dist[j], j});
			}
		}
	}
}

void Topsort()
{
	hh = 0, tt = -1;
	for (int i = 1; i <= N; i ++)
		if (!in[i])
			q[ ++ tt] = i;
	while (hh <= tt)
	{
		int u = q[hh ++];

		for (int i = hs[u]; ~i; i = ne[i])
		{
			int j = e[i];
			if ((-- in[j]) == 0)
				q[ ++ tt] = j;
		}
	}
}

signed main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	memset(h, -1, sizeof h);
	memset(hs, -1, sizeof hs);

	cin >> N >> M >> X1 >> Y1 >> X2 >> Y2;

	int u, v, c;
	while (M --)
	{
		cin >> u >> v >> c;
		add(h, u, v, c), add(h, v, u, c);
	}

	Dijkstra(X1, D[0]), Dijkstra(Y1, D[1]);
	Dijkstra(X2, D[2]), Dijkstra(Y2, D[3]);

	for (int i = 1; i <= N; i ++)
		for (int j = h[i]; ~j; j = ne[j])
		{
			int k = e[j];
			if (D[0][i] + w[j] + D[1][k] == D[0][Y1] && D[2][i] + w[j] + D[3][k] == D[2][Y2])
				add(hs, i, k, w[j]), in[k] ++;
		}

	Topsort();

	for (int it = 0; it <= tt; it ++)
	{
		int i = q[it];
		for (int j = hs[i]; ~j; j = ne[j])
		{
			int k = e[j];
			F[k] = max(F[k], F[i] + w[j]);
		}
	}

	int Result = 0;
	for (int i = 1; i <= N; i ++)
		Result = max(Result, F[i]);

	memset(hs, -1, sizeof hs);
	memset(F, 0, sizeof F);
	memset(in, 0, sizeof in);

	for (int i = 1; i <= N; i ++)
		for (int j = h[i]; ~j; j = ne[j])
		{
			int k = e[j];
			if (D[0][i] + w[j] + D[1][k] == D[0][Y1] && D[3][i] + w[j] + D[2][k] == D[2][Y2])
				add(hs, i, k, w[j]), in[k] ++;//, cout << i << " " << k << endl;
		}

	Topsort();

	for (int it = 0; it <= tt; it ++)
	{
		int i = q[it];
		for (int j = hs[i]; ~j; j = ne[j])
		{
			int k = e[j];
			F[k] = max(F[k], F[i] + w[j]);
		}
	}

	for (int i = 1; i <= N; i ++)
		Result = max(Result, F[i]);

	cout << Result << endl;

	return 0;
}

到了这里,关于【图论经典题目讲解】洛谷 P2149 Elaxia的路线的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 洛谷题单 -- 图论的简单入门

    图的存储 - 洛谷 这一题要考察图的存储方式 , 一般可以使用邻接矩阵 或 邻接表来存储 图的结点 和1 边的信息 ,详情请看代码 :  【深基18.例3】查找文献 - 洛谷 这题考察有向图的 dfs 和 bfs ,详情请看代码,如果用邻接矩阵的话一定会mle,只能够使用邻接表,我这里采用的是用

    2024年04月13日
    浏览(44)
  • 算法题目题单+题解——图论

    本文为自己做的一部分图论题目,作为题单列出,持续更新。 题单由题目链接和题解两部分组成,题解部分提供简洁题意,代码仓库:Kaiser-Yang/OJProblems。 对于同一个一级标题下的题目,题目难度尽可能做到递增。 题目链接:Luogu P3547 [POI2013] CEN-Price List 题解: 题目链接:

    2024年02月19日
    浏览(38)
  • 每天一道leetcode:1466. 重新规划路线(图论&中等&广度优先遍历)

    n 座城市,从 0 到 n-1 编号,其间共有 n-1 条路线。因此,要想在两座不同城市之间旅行只有唯一一条路线可供选择(路线网形成一颗树)。去年,交通运输部决定重新规划路线,以改变交通拥堵的状况。 路线用 connections 表示,其中 connections[i] = [a, b] 表示从城市 a 到 b 的一条

    2024年02月12日
    浏览(50)
  • PAT甲级图论相关题目

    PAT甲级图论相关题目: 分数 25 As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the length of each road between any pair of cities are marked on the map. When there is an emergency call to you from some o

    2024年01月21日
    浏览(53)
  • 力扣377周赛第三题(图论题目)

     

    2024年02月04日
    浏览(53)
  • 二叉树经典算法题目

    省略 输入一棵二叉树的根节点,求该树的深度。从根节点到叶节点依次经过的节点(含根、叶节点)形成树的一条路径,最长路径的长度为树的深度。 例如: 给定二叉树 [3,9,20,null,null,15,7] , 返回它的最大深度 3 。 思路:递归,当前数的深度等于左子数和右子树其中最大深

    2024年02月09日
    浏览(57)
  • 接口经典题目

    ​ White graces:个人主页 🙉专栏推荐:《Java入门知识》🙉 🙉 内容推荐:继承与组合:代码复用的两种策略🙉 🐹今日诗词: 人似秋鸿来有信,事如春梦了无痕。 🐹 目录 🌸一.题目🌸 🌸二.创建接口和类文件🌸 🍎1.USB接口🍎 🍎2.Mouse类🍎 🍎3.Keyboard类🍎 🌸三.笔记本类🌸

    2024年02月11日
    浏览(35)
  • 【C++】-多态的经典题目

    💖作者:小树苗渴望变成参天大树🎈 🎉作者宣言:认真写好每一篇博客💤 🎊作者gitee:gitee✨ 💞作者专栏:C语言,数据结构初阶,Linux,C++ 动态规划算法🎄 如 果 你 喜 欢 作 者 的 文 章 ,就 给 作 者 点 点 关 注 吧! 今天博主专门出一篇继承和多态的相关的题目,为了就是

    2024年02月15日
    浏览(36)
  • 【C语言】经典题目(二)

    C站的小伙伴们,大家好呀^^! 这一篇文章是C语言之经典题目,快来跟我一起进入C语言的世界吧!💞 C语言其他刷题篇在这里哦: 【C】语言经典题目(一) 【C语言】字符串—刷题篇 给出三角形的边长,求三角形的面积。 利用海伦公式求三角形面积 area=根号下 s*(s-a)*(s-b

    2024年02月07日
    浏览(43)
  • 动态内存面试的经典题目

    𝙉𝙞𝙘𝙚!!👏🏻‧✧̣̥̇‧✦👏🏻‧✧̣̥̇‧✦ 👏🏻‧✧̣̥̇:Solitary-walk       ⸝⋆   ━━━┓      - 个性标签 - :来于“云”的“羽球人”。 Talk is cheap. Show me the code ┗━━━━━━━  ➴ ⷯ 本人座右铭 :   欲达高峰,必忍其痛;欲戴王冠,必承其重。 👑💎💎👑

    2024年01月16日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包