自动搬运

查看原文

来自洛谷，原作者为

	lonlyn **

搬运于2025-08-24 21:23:02，当前版本为作者最后更新于2017-09-05 23:07:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

暴力做法就是n遍spfa，然后按照rank怼一遍就完事了。

不过能得多少分我就不知道了。。。。。。

有兴趣的同学可以试一下orz，我就不作了。

正解当然要对这个求解方案进行优化了啊。

怎么优化呢？orz

注意到rank似乎非常小，那就对rank搞点事情。

一般都能想到记录点x到rank为i的点集的最短路径，但我们为了以后方便可以扩展一下为 x到rank大于等于i的点集的最短路径 ，设为F[i][x]。

这样每次比较u，v就只要看一看dis(u,v)<F[rank[v]+1][u]。

我们对他优化一下orz。

以起点s开始找到一个点v，设v不关心s，则dis(s,v)>=F[rank[s]+1][v]；

若我们尝试把v扔进队列，假设松弛到u，

则dis(s,u)=dis(s,v)+dis(v,u);

But dis(s,v)>=F[rank[s]+1][v];

So dis(s,u)=dis(s,v)+dis(v,u)>=F[rank[s]+1][v]+dis(u,v)>=F[rank[s]+1][u];

所以此时u也是不对w感兴趣的点，我们还给他扔进去干嘛。。

答案不超过30n，复杂度不算高。

这道题告诉我们：spfa到一个不满足条件的点就不要把它扔到队列里面去了嘛。

（真理：暴力出奇迹）

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
struct node{
    int to;
    int v;
};
vector<node> edge;
vector<int> G[30010];
vector<int> o_edge[20];
int n,m;
int r[30010];
int u,v,t;
int far[20][30010];
int dis[30010];
bool vis[30010];
bool ok[30010];
int ans;

void add_edge(int from,int to,int v){
    edge.push_back((node){to,v});
    edge.push_back((node){from,v});
    int m=edge.size();
    G[from].push_back(m-2);
    G[to].push_back(m-1);
}

void o_spfa(int x){
    memset(vis,false,sizeof(vis));
    memset(far[x],0x3f,sizeof(far[x]));
    queue<int> q;
    for (int i=0;i<o_edge[x].size();++i){
        far[x][o_edge[x][i]]=0;
        q.push(o_edge[x][i]);
    }
    while (!q.empty()){
        int now=q.front();
        q.pop();
        vis[now]=false;
        for (int i=0;i<G[now].size();++i){
            node nxt=edge[G[now][i]];
            if (far[x][now]+nxt.v<far[x][nxt.to]){
                far[x][nxt.to]=far[x][now]+nxt.v;
                if (!vis[nxt.to]){
                    vis[nxt.to]=true;
                    q.push(nxt.to);
                }
            }
        }
    }
}

void wk(int x){
    for (int i=1;i<=n;++i){
        if (far[x][i]>far[x+1][i])
          far[x][i]=far[x+1][i];
    }
}

void spfa(int x){
    memset(vis,false,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));
    memset(ok,false,sizeof(ok));
    dis[x]=0;
    vis[x]=1;
    queue<int> q; q.push(x);
    while (!q.empty()){
        int now=q.front();
        q.pop();
        vis[now]=false;
        if (!ok[now]){
            ans++;
            ok[now]=true;
        }
        for (int i=0;i<G[now].size();++i){
            node nxt=edge[G[now][i]];
            if (dis[nxt.to]>dis[now]+nxt.v){
                dis[nxt.to]=dis[now]+nxt.v;
                if (!vis[nxt.to]&&dis[nxt.to]<far[r[x]+1][nxt.to]){
                    q.push(nxt.to);
                    vis[nxt.to]=true;
                }
            }
        }
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;++i){
        scanf("%d",&r[i]);
        o_edge[r[i]].push_back(i);
    }
    for (int i=1;i<=m;++i){
        scanf("%d%d%d",&u,&v,&t);
        add_edge(u,v,t);
    }
    for (int i=1;i<=10;++i) o_spfa(i);    
    for (int i=9;i>=1;--i) wk(i); 
    for (int i=1;i<=n;++i) spfa(i);
    cout<<ans;
    return 0;
}

从此你可以向别人炫耀说我用n遍spfa这种大暴力还能a题233