题解 P1261 【服务器储存信息问题】

· · 题解

服务器储存信息问题

先想暴力

设d[i, x]表示rank>=i的所有点到x的距离最小值

按照rank从大到小对每个点跑最短路，如果dis[y]<d[r[s]+1,y]则可以统计进答案，用dis[y]更新d[r[s],y]

优化

最容易想到的优化就是去除不必要的更新

设存在一条边x y v，正在用x节点更新其它节点且dis[x]>=d[r[s]+1,x]，那么dis[x]+v>=d[r[s]+1,y]一定成立，因为在rank>r[s]的某次更新中dis[y]可以从dis[x]+v更新d[r[s]+1,y]+v<=d[r[s]+1,x]

所以我们不需要更新dis[x]>=d[r[s]+1,x]的节点，最后答案就是每次更新的节点数之和

代码（没有使用滚动数组，跑得比较慢，空间比较大）

#include<bits/stdc++.h>
using namespace std;
inline int gi() {
    register int x=0,op=1,c;
    while(c=getchar(),c<'0'||c>'9')if(c=='-')op=-op;
    x=c^48;
    while(c=getchar(),c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48);
    return x*op;
}
int head[30001], nxt[300001], ver[300001], val[300001], tot = 1;
void add(int x, int y, int z) {
    ver[++ tot] = y, val[tot] = z, nxt[tot] = head[x], head[x] = tot;
    ver[++ tot] = x, val[tot] = z, nxt[tot] = head[y], head[y] = tot;
}
int n, m;
int r[30001];
int d[12][30001];
priority_queue<pair<int, int> >q;
int dis[30001];
bool v[30001];
int ans = 0;
void dij(int s) {
    memset(dis, 0x7f, sizeof(dis));
    memset(v, 0, sizeof(v));
    dis[s] = 0;
    q.push(make_pair(0, s));
    int x;
    while(! q.empty()) {
        x = q.top().second;
        q.pop();
        if(v[x])continue;
        ans ++ ;
        v[x] = 1;
        for(int i = head[x], y; i; i = nxt[i])
            if(! v[ver[i]] && dis[y = ver[i]] > dis[x] + val[i] && dis[x] + val[i] < d[r[s] + 1][ver[i]]) {
                dis[y] = dis[x] + val[i];
                d[r[s]][y] = min(dis[y], d[r[s]][y]);
                q.push(make_pair(- dis[y], y));
            }
    }
}
int main() {
    n = gi(), m = gi();
    for(int i = 1; i <= n; i ++)
        r[i] = gi();
    for(int i = 1, x, y; i <= m; i ++)
        x = gi(), y = gi(), add(x, y, gi());
    memset(d, 0x7f, sizeof(d));
    for(int i = 10; i; i --) {
        for(int j = 1; j <= n; j ++)
            if(i == r[j])d[i][j] = 0;
        for(int j = 1; j <= n; j ++)
            if(r[j] == i)dij(j);
        memcpy(d[i-1], d[i], sizeof(d[i]));
    }
    printf("%d\n", ans);
    return 0;
}