洛谷P1608题解

原题

P1608 路径统计

思路概述

题意分析

带有向边判重的单源最短路径与最短路径计数。

思路分析

首先排除已经死掉的SPFA。

考虑Dijkstra，但由于需要判重边，所以直接邻接矩阵存图。笔者不建议邻接矩阵判重后再用链式前向星存图（ \(100→53\) 血的教训）。

算法实现

关于邻接矩阵存图

由于求最短路，所以两个点之间的同一条有向边只需要保留边权最小的一条。

代码如下：

for(RI i=1,x,y,w;i<=m;++i)
	{
		cin >> x >> y >> w;
		dist[x][y]=min(dist[x][y],w);
	}

Dijkstra的线段树实现

本题可以用堆优化，但是笔者决定介绍Dijkstra的线段树实现方式。

从算法原理入手：Dijkstra算法的流程是每次选取离起点最近的点，并搜索所有出边，松弛与其相连的其他点。最后在松弛操作中求得起点到终点的最短路径。而每次选取最近点的操作，就是线段树的优化对象（与堆优化效果一致）。

线段树的实现与其他权值线段树没有太大差别。但由于每次只进行单点修改，所以不需要懒标记，只需要区间最小值上传。

值得注意的是，每次取出最近点后需要将该点从集合中删除（对应堆优化中的出堆）。在线段树中，向取出的下标上传一个极大值，使其不会再被上传，即达到类似效果。

关于路径计数

最短路径计数考虑两种情况。

为方便表述，设当前选定的最近点为 \(u\) ，与起点最短路径长度为 \(dis_u\) ；搜索到的出边为 \(i\) ，权值为 \(w_i\) ；边的另一端点 \(v\) ，与起点最短路径长度 \(dis_v\) ；两点的最短路径数分别为 \(cnt_u,cnt_v\)。

当 \(dis_v>w_i+dis_u\) ，此时点 \(v\) 的最短路径被更新，其最短路径数也要被其前驱点 \(u\) 的最短路径数覆盖，即 \(cnt_v=cnt_u\) 。

当 \(dis_v=w_i+dis_u\) ，说明在点 \(u\) 松弛之前，点 \(v\) 已经存在长度相同的最短路径，此时到达点 \(v\) 的最短路径即为当前两个点最短路径数的和，即 \(cnt_v=cnt_u+cnt_v\) 。

AC code

因为实现太烂，代码凑合看看就行。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#define RI register int
#define RN register node
using namespace std;
const int maxn=2e3+10;
typedef struct node
{
	int dis;
	int pos;
};
typedef struct
{
	int l,r;
	node data;
}tree;
tree e[maxn<<2];
int n,m,cnt;
int fir[maxn],dis[maxn],dist[maxn][maxn],rec[maxn];
bool v[maxn];
inline node getmin(node x,node y);/*返回距离最小的结点*/
inline void push_up(int p);/*区间最小值上传*/
inline void build(int p,int l,int r);/*建树*/
inline void update(int p,node opt);/*上传值（在本题中上传最大整数 类似于堆优化中的出堆）*/
inline node query(int p,int l,int r);/*查询最小值*/
inline void dijkstra(int st);/*Dijkstra板子*/
int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin >> n >> m;
	memset(dist,0x3f3f3f3f,sizeof(dist));
	for(RI i=1,x,y,w;i<=m;++i)
	{
		cin >> x >> y >> w;
		dist[x][y]=min(dist[x][y],w);/*因为需要判重 所以直接邻接矩阵存图*/ 
	}
	dijkstra(1);
	if(dis[n]==0x3f3f3f3f) puts("No answer");
	else cout << dis[n] << " " << rec[n];	
	return 0;
}
inline node getmin(node x,node y)
{
	if(x.dis>1;
		build(p<<1,l,mid);build(p<<1|1,mid+1,r);
		push_up(p);
	}
	return;
}
inline void update(int p,node opt)
{
	if(e[p].l>=opt.pos && e[p].r<=opt.pos) e[p].data=opt;
	else
	{
		RI mid=(e[p].l+e[p].r)>>1;
		if(mid>=opt.pos) update(p<<1,opt);
		else update(p<<1|1,opt);
		push_up(p);
	}
	return;
}
inline node query(int p,int l,int r)
{
	if(e[p].l>=l && e[p].r<=r) return e[p].data;
	else
	{
		RI mid=(e[p].l+e[p].r)>>1;
		RN ret=(node){0x3f3f3f3f,1};
		if(mid>=l) ret=getmin(ret,query(p<<1,l,r));
		if(middis[temp.pos]+dist[temp.pos][j])
			{
				dis[j]=dis[temp.pos]+dist[temp.pos][j];rec[j]=rec[temp.pos];/*最小权值更新 当前结点最短路径数等于其前驱的最短路径数*/
				update(1,(node){dis[j],j});
			}
			else if(dis[j]==dis[temp.pos]+dist[temp.pos][j]) rec[j]+=rec[temp.pos];/*不更新最小权值 但是更新最短路径数*/
	}
	return;
}