題目背景

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?m)$（$k$ 為常數）。
  初始化距離為 0x7fffffff（32 位整數最大值），但實際用 long long 存儲。
  距離累加

• dp1[i] += dp[i] 將每個特殊點的最短路徑累加到全局數組。
  最終 dp1[i] 表示所有特殊點到節點 $i$ 的距離和。
  無向圖處理

add(x, y, c);  // 添加雙向邊
add(y, x, c);

復雜度分析

• 時間復雜度：$O(n?k?m)$
• 其中 $n$ 為特殊點數量，$m$ 為邊數，$k$ 是 SPFA 的平均松弛次數。
• 空間復雜度：$O(a+m)$
• 鄰接表存儲圖，數組大小與節點數 $a$ 成正比。

適用場景

• 適合稀疏圖（$m?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;
}