题目分析

我们需要确定城市之间的合作意愿关系。具体来说，城市 $B$ 愿意与城市 $A$ 建立合作关系，当且仅当对于所有满足 $R(C) > R(B)$ 的城市 $C$，都有 $d(A, C) > d(A, B)$。其中 $d(A, B)$ 表示城市 $A$ 和 $B$ 之间的最短路径距离，$R(C)$ 表示城市 $C$ 的某种属性值（如优先级或权重）。

解题思路

1. 问题转化：

   • 将原问题转化为：城市 $B$ 愿意与城市 $A$ 合作的条件是，所有 $R$ 值比 $B$ 大的城市 $C$ 到 $A$ 的距离都严格大于 $B$ 到 $A$ 的距离。
   • 定义 $lim[A]$ 为所有 $R$ 值比 $A$ 大的城市中，到 $A$ 的最小距离：$$lim[A] = \min \{ d(A, C) \mid R(C) > R(A) \}$$

2. 关键观察：

   • 由于 $d(A, C) = d(C, A)$（无向图），$lim[A]$ 可以理解为 $A$ 到所有更高优先级城市的最小距离。
   • 合作条件可以重新表述为：$$d(A, B) < lim[A]$$
   • 即 $B$ 到 $A$ 的距离必须小于 $A$ 到所有更高优先级城市的最小距离。

3. 算法设计：

   • 按 $R$ 值降序枚举源点：
     • 从 $R$ 值最大的城市开始，逐步处理 $R$ 值较小的城市。
     • 对于每个源点 $B$，使用 Dijkstra 算法 计算它到其他城市的最短路径 $dist[A]$。
   • 松弛条件修改：
     • 只有当 $dist[A] < lim[A]$ 时，才允许更新 $dist[A]$ 并将 $A$ 加入优先队列。
     • 这样保证 只有满足合作条件的城市才会被处理。
   • 贡献统计：
     • 每次成功松弛的点 $A$ 对答案的贡献为 $1$（即 $B$ 愿意与 $A$ 合作）。

关键优化

• 预处理 $lim$ 数组：
  • 先对所有城市按 $R$ 值排序，计算每个城市的 $lim[A]$。
  • 可以利用 多源最短路径算法（如 BFS 或 Dijkstra） 高效计算。
• 动态更新 $lim$：
  • 由于按 $R$ 降序处理，$lim[A]$ 可以动态维护（每次处理完一个 $R$ 值后更新）。

复杂度分析

• 时间复杂度：
  • 预处理 $lim$ 的时间为 $O(n \log n)$（排序）加上 $O(n \cdot \text{最短路径计算复杂度})$。
  • 主算法部分为 $O(\text{ans} \cdot \log n)$，其中 $\text{ans}$ 是总合作对数。
• 空间复杂度：
  • 需要存储图结构、$dist$ 数组和 $lim$ 数组，空间为 $O(n + m)$。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=3e4+10;
const int INF=0x3f3f3f3f;
int n,m,hd[N],r[N],tot,nowrank,dis[N],lim[N],stack[N],tp,top,ans,minr[N];
struct Edge{
	int v,w,nx;
}e[N*10];
struct Heap{
	int x,w;
	Heap(void){}
	Heap(int _x,int _w):x(_x),w(_w){}
}heap[100*N];
void add(int u,int v,int w)
{
	e[++tot].v=v;
	e[tot].w=w;
	e[tot].nx=hd[u];
	hd[u]=tot;
}
bool cmp(const Heap&a,const Heap&b)
{
	return a.w>b.w||(a.w==b.w&&r[a.x]<r[b.x]);
}
void dijk()
{
	while(top)
	{
		Heap sta=heap[1];
		pop_heap(heap+1,heap+top+1,cmp);
		top--;
		if(sta.w!=dis[sta.x])continue;
		stack[++tp]=sta.x;
		for(int i=hd[sta.x];i;i=e[i].nx)
		{
			if(r[e[i].v]>nowrank)continue;
			if(dis[e[i].v]>sta.w+e[i].w&&lim[e[i].v]>sta.w+e[i].w)
			{
				dis[e[i].v]=sta.w+e[i].w;
				heap[++top]=Heap(e[i].v,dis[e[i].v]);
				push_heap(heap+1,heap+top+1,cmp);
			}
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	    scanf("%d",&r[i]);
	for(int i=1,u,v,w;i<=m;i++)
	    scanf("%d%d%d",&u,&v,&w),add(u,v,w),add(v,u,w);
	memset(dis,0x3f,sizeof(dis));
	memset(lim,0x3f,sizeof(lim));
	for(int i=10;i;i--)
	{
		nowrank=i;
		memset(minr,0x3f,sizeof(minr));
		for(int j=1;j<=n;j++)
		    if(r[j]==i)
		    {
		    	heap[++top]=Heap(j,0);
		    	dis[j]=0;
		    	dijk();
		    	for(;tp;tp--)
		    	{
		    		int k=stack[tp];
		    		if(lim[k]>dis[k])ans++;
		    		minr[k]=min(minr[k],dis[k]);
		    		dis[k]=INF;
				}
			}
		for(int j=1;j<=n;j++)
		    lim[j]=min(minr[j],lim[j]);
	}
	printf("%d\n",ans);
	return 0;
}