洛谷 P1629 邮递员送信

算法标签: 图论，最短路

题目

题目描述

有一个邮递员要送东西，邮局在节点1.他总共要送N-1样东西，其目的地分别是2~N。由于这个城市的交通比较繁忙，因此所有的道路都是单行的，共有M条道路，通过每条道路需要一定的时间。这个邮递员每次只能带一样东西。求送完这N-1样东西并且最终回到邮局最少需要多少时间。

输入格式

第一行包括两个整数N和M。

第2到第M+1行，每行三个数字U、V、W，表示从A到B有一条需要W时间的道路。满足1<=U,V<=N,1<=W<=10000,输入保证任意两点都能互相到达。

【数据规模】

对于30%的数据，有1≤N≤200;

对于100%的数据，有1≤N≤1000,1≤M≤100000。

输出格式

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

输入输出样例

输入 #1

输出 #1

题解：

这道题可以说很坑了，坑点就在于有向图！！！我们可以发现按照题中描述我们需要从起始点先到某个点，在从某个点回到起始点，反复循环。但是由于是有向图，所以去的时候的最短路不一定就是回来时候的最短路，由于如果求n个点的最短路，或者多源单点最短路，时间上是承受不了的，所以这个问题成为整个题的难点所在，那么怎么处理？？？

大致的思路是这样，把我们从起点（邮局）开始的一边最短路定为正向，那么我们回来就相当于一次反向求最短路。

按照我们正常想法是从N个点向起始点都跑一遍最短路（是不是想起了Floyd），那么加入我们反向建图，这就变成了从起始点向N个重点跑最短路，就又变成了另外一组单源最短路，在时间上是可以接受的。

因为半死不活的SPFA算法和它（在不稳定方面）~~极为优秀~~的时间复杂度，个人放弃了这个算法，所以没有写SPFA的题解（从题目中M的数据范围就放弃了），正常使用堆优化Dijkstra，代码如下：

AC代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;
const int M = 100100;

int n, m, ans, vis[N], dis[N], fvis[N], fdis[N];
int tot, to[M], nex[M], val[M], head[N];
int ftot, fto[M], fnex[M], fval[M], fhead[N];

void add(int x, int y, int z)
{
	to[ ++ tot] = y;
	val[tot] = z;
	nex[tot] = head[x];
	head[x] = tot;
	fto[ ++ ftot] = x;
	fval[ftot] = z;
	fnex[ftot] = fhead[y];
	fhead[y] = ftot;
}
priority_queue < pair<int, int> > q;
void dijkstra(int s)
{
	memset(dis, 0x3f, sizeof dis);
	memset(vis, 0, sizeof vis);
	dis[s] = 0;
	q.push(make_pair(0, s));
	while(!q.empty())
	{
		int x = q.top().second;
		q.pop();
		if (vis[x])
			continue ;
		vis[x] = 1;
		for (int i = head[x]; i; i = nex[i])
		{
			if (dis[to[i]] > dis[x] + val[i])
			{
				dis[to[i]] = dis[x] + val[i];
				q.push(make_pair(-dis[to[i]], to[i]));
			}
		}
	}
}
void fdijkstra(int s)
{
	memset(fdis, 0x3f, sizeof fdis);
	memset(fvis, 0, sizeof fvis);
	fdis[s] = 0;
	q.push(make_pair(0, s));
	while(!q.empty())
	{
		int x = q.top().second;
		q.pop();
		if (fvis[x])
			continue ;
		fvis[x] = 1;
		for (int i = fhead[x]; i; i= fnex[i])
		{
			if (fdis[fto[i]] > fdis[x] + fval[i])
			{
				fdis[fto[i]] = fdis[x] + fval[i];
				q.push(make_pair(-fdis[fto[i]], fto[i]));
			}
		}
	}
} 
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i ++ )
	{
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		add(x, y, z);
	}
	dijkstra(1);
	fdijkstra(1);
	for (int i = 2; i <= n; i ++ )
	{
		ans += dis[i] + fdis[i];
	}
	printf("%d
", ans);
	return 0;
}