首页 > 其他分享 >【图论】最短路练习——P1629邮递员送信

【图论】最短路练习——P1629邮递员送信

时间:2024-04-23 17:13:19浏览次数:25  
标签:10 图论 int leq 邮递员 push P1629 d1

邮递员送信

题目描述

有一个邮递员要送东西,邮局在节点 \(1\)。他总共要送 \(n-1\) 样东西,其目的地分别是节点 \(2\) 到节点 \(n\)。由于这个城市的交通比较繁忙,因此所有的道路都是单行的,共有 \(m\) 条道路。这个邮递员每次只能带一样东西,并且运送每件物品过后必须返回邮局。求送完这 \(n-1\) 样东西并且最终回到邮局最少需要的时间。

输入格式

第一行包括两个整数,\(n\) 和 \(m\),表示城市的节点数量和道路数量。

第二行到第 \((m+1)\) 行,每行三个整数,\(u,v,w\),表示从 \(u\) 到 \(v\) 有一条通过时间为 \(w\) 的道路。

输出格式

输出仅一行,包含一个整数,为最少需要的时间。

样例 #1

样例输入 #1

5 10
2 3 5
1 5 5
3 5 6
1 2 8
1 3 8
5 3 4
4 1 8
4 5 3
3 5 6
5 4 2

样例输出 #1

83

提示

对于 \(30\%\) 的数据,\(1 \leq n \leq 200\)。

对于 \(100\%\) 的数据,\(1 \leq n \leq 10^3\),\(1 \leq m \leq 10^5\),\(1\leq u,v \leq n\),\(1 \leq w \leq 10^4\),输入保证任意两点都能互相到达。

思路

迪杰斯特拉模板题,注意题目中的边为单向边,解决问题可以正反向建边。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct node{
	int v,w;
};
priority_queue<pair<int,int>> q;
priority_queue<pair<int,int>> qq;
int n,m;
vector<node> p[N];
vector<node> pp[N];
int ans;
int d[N],vis[N],pre[N];
int d1[N],vis1[N],pre1[N];
void dijisk(int s)
{
	for(int i=0;i<=n;i++) d[i]=0x3f3f3f3f;
	d[s]=0;
    q.push({0,s});
    while(q.size())
    {
    	auto t=q.top();
    	q.pop();
    	int u=t.second;
    	if(vis[u]) continue;
    	vis[u]=1;
    	for(auto it:p[u])
    	{
    		int v=it.v;
    		int w=it.w;
    		if(d[v]>d[u]+w)
    		{
    			d[v]=d[u]+w;
    			pre[v]=u;
    			q.push({-d[v],v});
    		}
    	}
    }
}
void dijisk1(int s)
{
	for(int i=0;i<=n;i++) d1[i]=0x3f3f3f3f;
	d1[s]=0;
    qq.push({0,s});
    while(qq.size())
    {
    	auto t=qq.top();
    	qq.pop();
    	int u=t.second;
    	if(vis1[u]) continue;
    	vis1[u]=1;
    	for(auto it:pp[u])
    	{
    		int v=it.v;
    		int w=it.w;
    		if(d1[v]>d1[u]+w)
    		{
    			d1[v]=d1[u]+w;
    			pre1[v]=u;
    			qq.push({-d1[v],v});
    		}
    	}
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
    	int a,b,c;
    	cin>>a>>b>>c;
    	p[a].push_back({b,c});
    	pp[b].push_back({a,c});
    }
    dijisk(1);
    dijisk1(1);
    for(int i=1;i<=n;i++) ans+=d[i];
    for(int i=1;i<=n;i++) ans+=d1[i];
    	cout<<ans;
	return 0;
}```

标签:10,图论,int,leq,邮递员,push,P1629,d1
From: https://www.cnblogs.com/marshuo/p/18153280

相关文章

  • 图论理论基础
    Smiling&Weeping ----前方的风景好像很美...图论基础总结图论是研究图的结构和性质的数学分支。图是一种由节点(顶点)和边组成的数学结构,其中节点表示实体,边表示实体之间的关系。图论可以应用于解决许多现实世界中的问题,例如社交网络分析、交通......
  • [题解]P1629 邮递员送信
    好久不写图论题了,Dijkstra都花了好长时间捡起来……之前也没有接触过反图的概念。这个题算是我重拾图论知识以来的第一题了。__φ(..)P1629邮递员送信Dijkstra是单源最短路的算法。但这个题除了要求节点\(1\)到其他节点的距离,还要知道其他节点回到节点\(1\)的距离。如果我们每个......
  • [学习笔记] 树上差分 - 图论
    前置知识:树,LCA,前缀和与差分边差分这个名字是在网上看到的,不理解为什么要叫这么一个名字,可能是因为它与树链修改有关。当然,用于树链修改单点查询非常方便~看这个图,该图是以点1为根进行DFS的。如果我们要把从3->4这条树链上所有的点统统加上1,可以都转化为对到根节点的......
  • [学习笔记] LCA - 图论
    [NOIP2013提高组]货车运输最大生成树+LCA+倍增好家伙,这道题我写了一个晚上,调了两个晚上,对于这道题我颇有感触。但这道题确实好,实实在在的蓝题,让我发现了许多关于LCA的问题。首先,这个题给的是一个无向图,并不是个树,为了减少运算量,我们可以把它变成一个树。运用Kruskal算法生......
  • 图论杂题
    Codeforces1572D-BridgeClub题意给出\(n\),有\(2^n\)个点,点权已给出。要求只有两个点的编号的二进制上有且只有一个位置不同时,这两个点有连边。求原图最多选择\(k\)条边的最大(点)权匹配。\(n\le20;k\le100\)Sol考虑边连接的两个点的\(\mathrm{popcount}\)一定不......
  • acwing算法全总结——搜索与图论
    acwing算法全总结——搜索与图论dfsbfs树与图的深度优先遍历树与图的广度优先遍历拓扑排序最短路问题dijkstra最短路bellman-ford最短路spfa最短路floyd最短路最小生成树prim最小生成树kruskal最小生成树二分图搜索与图论这一章算是对数据结构与算法的进阶提升吧,它......
  • 2024.4.9 图论补题
    P3225[HNOI2012]矿场搭建如果没有割点,至少需要建立两个出口如果只有一个割点,只需要设立一个出口如果有两个及以上个割点,则无需建立,可以直接到达其他联通块#include<cmath>#include<queue>#include<cstdio>#include<vector>#include<cstdlib>#include<cstring>#include......
  • 2024.04.09 图论复习
    2024.04.09图论复习P3403跳楼机同余最短路模板题。设\(d_i\)表示只使用向上移动\(y\)层或\(z\)层两种功能,所能达到的最低楼层\(p\),其中\(p\mod\x=i\)。两种连边方式:\(i\)向\((i+y)mod\x\)连权值为\(y\)的边;\(i\)向\((i+z)mod\x\)连权值为\(z\)的......
  • 图论学习笔记
    Dijkstra单源最短路径堆优化。注意要定义成小根堆,而priority_queue默认大根堆再就是每个点最多入队一次,可以用vis数组记录证明:如果已经出队,说明队列中全都是val值比他大的(负权边?),这样他的val值一定已经是最终值了;如果没有入队,进行更改之后会在堆中体现,不需要担心之后还会更......
  • 【题单】 洛谷图论题单
    这里写目录标题updata普及-普及/提高-普及+/提高提高+/省选-省选/NOI−NOI/NOI+/CTSCupdata2024.03.31发布此文章普及-P1359租用游艇P1636Einstein学画画(数据有误)P1700[USACO19OPEN]MilkFactoryBB3613图的存储与出边的排序B3643图的存储B3644【模......