题面

Sol

我们可以考虑每种\(rank\)的点\(u\)会被哪些点\(v\)感兴趣

如果\(dis[u][v]<\)所有满足\(rank\)大于\(rank[u]\)的点到\(v\)的距离

那么\(v\)一定对\(u\)感兴趣

我们可以先\(10\)遍最短路，处理出每种\(rank\)的点到所有点的最短路

计\(f[i][j]\)表示满足\(i\le rank\)的点到所有点的最短路

然后每次从一个点\(u\)出发，寻找对它感兴趣的点\(v\)

如果发现\(f[rank[u]+1][v]\le dis[u][v]\)

那么\(v\)不对\(u\)感兴趣，而且所有\(v\)能松弛到的点也都不会

那么可以\(SPFA\)，每次不满足要求了就不丢进队列

复杂度是\(O(ans+10n)\)的，可以接受

# include <bits/stdc++.h>

# define RG register

# define IL inline

# define Fill(a, b) memset(a, b, sizeof(a))

using namespace std;

const int _(3e4 + 5);

const int INF(1e9);

typedef long long ll;

IL int Input(){

    RG int x = 0, z = 1; RG char c = getchar();

    for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;

    for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);

    return x * z;

}

int n, m, rk[_], first[_], cnt, f[15][_], vis[_], ans, dis[_], use[_];

struct Edge{

	int to, next, w;

} edge[_ * 10];

struct Data{

	int u, d;

	IL int operator <(RG Data A) const{

		return d > A.d;

	}

};

priority_queue <Data> Q;

queue <int> Deq;

IL void Add(RG int u, RG int v, RG int w){

	edge[cnt] = (Edge){v, first[u], w}, first[u] = cnt++;

}

IL void Dijkstra(RG int p, RG int *dis){

	for(RG int i = 1; i <= n; vis[i] = 0, ++i)

		if(rk[i] == p) dis[i] = 0, Q.push((Data){i, 0});

		else dis[i] = INF;

	while(!Q.empty()){

		RG Data x = Q.top(); Q.pop();

		if(vis[x.u]) continue;

		vis[x.u] = 1;

		for(RG int e = first[x.u]; e != -1; e = edge[e].next){

			RG int v = edge[e].to, w = edge[e].w;

			if(x.d + w < dis[v]) Q.push((Data){v, dis[v] = x.d + w});

		}

	}

}

IL int SPFA(RG int x){

	RG int ret = 0;

	for(RG int i = 1; i <= n; ++i) dis[i] = INF, use[i] = vis[i] = 0;

	Deq.push(x), dis[x] = 0, vis[x] = 1;

	while(!Deq.empty()){

		RG int u = Deq.front(); Deq.pop();

		if(!use[u]) use[u] = 1, ++ret;

		for(RG int e = first[u]; e != -1; e = edge[e].next){

			RG int v = edge[e].to, w = edge[e].w;

			if(dis[u] + w < dis[v]){

				dis[v] = dis[u] + w;

				if(!vis[v] && f[rk[x] + 1][v] > dis[v]) vis[v] = 1, Deq.push(v);

			}

		}

		vis[u] = 0;

	}

	return ret;

}

int main(RG int argc, RG char* argv[]){

	n = Input(), m = Input();

	for(RG int i = 1; i <= n; ++i) rk[i] = Input(), first[i] = -1, f[11][i] = INF;

	for(RG int i = 1; i <= m; ++i){

		RG int u = Input(), v = Input(), w = Input();

		Add(u, v, w), Add(v, u, w);

	}

	for(RG int i = 10; i; --i){

		Dijkstra(i, f[i]);

		for(RG int j = 1; j <= n; ++j) f[i][j] = min(f[i][j], f[i + 1][j]);

	}

	for(RG int i = 1; i <= n; ++i) ans += SPFA(i);

	printf("%d\n", ans);

    return 0;

}

巴特西

Luogu1261: 服务器储存信息问题

题面

Sol

最新文章

热门文章