P1967 [NOIP 2013 提高组] 货车运

题目背景

NOIP2013 提高组 D1T3

题目描述

A 国有 $n$ 座城市，编号从 $1$ 到 $n$，城市之间有 $m$ 条双向道路。每一条道路对车辆都有重量限制，简称限重。

现在有 $q$ 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

输入格式

第一行有两个用一个空格隔开的整数 $ n,m$，表示 A 国有 $ n$ 座城市和 $m$ 条道路。

接下来 $m$ 行每行三个整数 $x,y,z$，每两个整数之间用一个空格隔开，表示从 $x $ 号城市到 $ y $ 号城市有一条限重为 $z$ 的道路。
注意： $x\ne y$，两座城市之间可能有多条道路 。

接下来一行有一个整数 $q$，表示有 $q$ 辆货车需要运货。

接下来 $q$ 行，每行两个整数 $x,y$，之间用一个空格隔开，表示一辆货车需要从 $x$ 城市运输货物到 $y$ 城市，保证 $x\ne y$

输出格式

共有 $q$ 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。
如果货车不能到达目的地，输出 $-1$。

输入输出样例 #1

输入 #1

4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3

输出 #1

3
-1
3

说明/提示

对于 $30\%$ 的数据，$1\le n<1000$，$1\le m<10,000$，$1\le q<1000$；

对于 $60\%$ 的数据，$1\le n<1000$，$1\le m<5\times 10^4$，$1\le q<1000$；

对于 $100\%$ 的数据，$1\le n<10^4$，$1\le m<5\times 10^4$，$1 \le q< 3\times 10^4 $，$0\le z\le 10^5$。

算法思路

• 问题转换

• 设特殊点集合为 $S$，目标函数为： $$f(v)=\sum _{s\in S}\text{dist}(s,v)$$

• 其中 $\text{dist}(s,v)$ 表示节点 $s$ 到 $v$ 的最短路径距离。需要找到 KaTeX parse error: Expected group after '^' at position 2: v^̲ 使得： $$v^{=}\arg \underset{1\le v\le a}{\min }f(v)$$

• 核心算法

• 使用 SPFA 算法（Shortest Path Faster Algorithm）计算每个特殊点到所有节点的最短路径。
  维护全局数组 dp1[] 累加所有特殊点到各节点的距离和： $$\text{dp1}[v]=\sum _{s\in S}\text{dist}(s,v)$$

• 最终遍历 dp1[] 取最小值： $$\text{ans}=\underset{v\in [1,a]}{\min }\text{dp1}[v]$$

关键点说明

• SPFA 优化

• 使用队列避免重复松弛，时间复杂度平均 $O(k\cdot m)$（$k$ 为常数）。
  初始化距离为 0x7fffffff（32 位整数最大值），但实际用 long long 存储。
  距离累加

• dp1[i] += dp[i] 将每个特殊点的最短路径累加到全局数组。
  最终 dp1[i] 表示所有特殊点到节点 $i$ 的距离和。
  无向图处理

add(x, y, c);  // 添加双向边
add(y, x, c);

复杂度分析

• 时间复杂度：$O(n\cdot k\cdot m)$
• 其中 $n$ 为特殊点数量，$m$ 为边数，$k$ 是 SPFA 的平均松弛次数。
• 空间复杂度：$O(a+m)$
• 邻接表存储图，数组大小与节点数 $a$ 成正比。

适用场景

• 适合稀疏图（$m\ll a^2$）且特殊点数量 $n$ 较小的场景。
• 若 $n$ 或 $a$ 过大（$>10^4$），可改用 Dijkstra 堆优化（需非负权边）。
• 注意：当图存在负权边时 SPFA 仍有效，但需确保无负权环（题目未说明时通常假设无环）。

详细代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int dp[N],dp1[N],n,m,a,b,x,y,c,h[N],w[N],to[N],ne[N],tot,num[N];
bool vis[N];
void add(int a,int b,int c)
{
	tot++;
	ne[tot]=h[a];
	h[a]=tot;
	to[tot]=b;
	w[tot]=c;
}
void spfa(int x)
{
	fill(dp+1,dp+1+a,0x7fffffff);
	fill(vis+1,vis+1+a,0);
	dp[x]=0;
	queue<int>q;
	q.push(x);
	vis[x]=1;
	while(!q.empty())
	{
		int j=q.front();q.pop();vis[j]=0;
		for(int i=h[j];i;i=ne[i])
		{
			int jj=to[i];
			if(dp[jj]>dp[j]+w[i])
			{
				dp[jj]=dp[j]+w[i];
				if(!vis[jj])
				{
					vis[jj]=1;
					q.push(jj);
				}
			}
		}
	}
//	cout<<dp[8]<<'\n';
	for(int i=1;i<=a;i++)
		dp1[i]+=dp[i];
}
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	memset(dp1,0,sizeof(dp1));
	cin>>n>>a>>m;
	for(int i=1;i<=n;i++)
		cin>>num[i];
	for(int i=1;i<=m;i++)
	{
		cin>>x>>y>>c;
		add(x,y,c);
		add(y,x,c);
	}
	for(int i=1;i<=n;i++)
		spfa(num[i]);
//	for(int i=1;i<=n;i++)
//		cout<<num[i]<<'\n';
//	for(int i=1;i<=a;i++)
//		cout<<dp[i]<<'\n';
	int ans=1e12;int sf=0;
	for(int i=1;i<=a;i++)
	{
		if(ans>dp1[i])
			sf=i;
		ans=min(ans,dp1[i]);
	}
//	cout<<b;
//	cout<<ans;
//	cout<<sf<<'\n';
	cout<<ans;
	return 0;
}