E1. Distance Tree (easy version) 题解(思维)

题目链接

题目思路

这个题目的思路就是连\(1,j\)一个长度为\(x\)的边

其实就是有个中转点

\(dep[i]=min(dis[1][i],dis[i][j]+x)\)

那么如果\(x\leq dis[1][i]-dis[i][j]\;dep[i]=dis[i][j]+x\) 反之亦然

对于中转点利用双指针的思想写写

说的感觉好差，看代码可能可以看懂

代码

#include
#define ll long long
#define fi first
#define se second
using namespace std;
const int maxn=3e3+5;
int n;
int pr[maxn];
int dis[maxn][maxn];
int prea[maxn],sufb[maxn];
vector g[maxn];
struct node{
    int a,b;
// a 1到j的路径
// b i到j的路径
};
node e[maxn];
void bfs(int id){
    dis[id][id]=0;
    queue que;
    que.push(id);
    while(!que.empty()){
        int now=que.front();
        que.pop();
        for(auto x:g[now]){
            if(dis[id][x]!=-1) continue;
            dis[id][x]=dis[id][now]+1;
            que.push(x);
        }
    }
}
bool cmp(node a,node b){
    return a.a-a.b=1;j--){
                sufb[j]=max(sufb[j+1],e[j].b);
            }
            int pos=0;
            for(int j=1;j<=n;j++){
                while(pos