cf1051F. The Shortest Statement(最短路)

题意

题目链接

题意:给出一张无向图,每次询问两点之间的最短路,满足$m - n <= 20$

$n, m, q \leqslant 10^5$

Sol

非常好的一道题。

首先建出一个dfs树。

因为边数-点数非常少,所以我们可以对于某些非树边特殊考虑。

具体做法是:对于非树边连接的两个点,暴力求出它们到所有点的最短路

对于询问的$(x, y)$

用树上的边,以及非树边连接的点到他们的最短路之和更新答案

由于边数的限制,非树边连接的点不会超过$2*(m - (n - 1)) = 42$个

#include<bits/stdc++.h>
#define Pair pair<int, int>
#define MP(x, y) make_pair(x, y)
#define fi first
#define se second
#define LL long long 
using namespace std;
const int MAXN = 2 * 1e5 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M, Q, head[MAXN], num = 0, vis[MAXN], fa[MAXN][21], dep[MAXN], happen[MAXN];
LL dis[50][MAXN], Tdis[MAXN];
vector<int> p;
struct Edge {
    LL u, v, w, f, nxt;
}E[MAXN];
inline void AddEdge(int x, int y, int z) {
    E[num] = (Edge) {x, y, z, 0, head[x]};
    head[x] = num++;
}
void dfs(int x, int _fa) {
    vis[x] = 1; dep[x] = dep[_fa] + 1;
    for(int i = head[x]; ~i; i = E[i].nxt) {
        int to = E[i].v;
        if(vis[to]) continue;
        E[i].f = E[i ^ 1].f = 1;
        Tdis[to] = Tdis[x] + (LL)E[i].w;
        fa[to][0] = x;
        dfs(to, x);
    }
} 
void Dij(int x, int id) {
    memset(dis[id], 0x7f, sizeof(dis[id])); dis[id][x] = 0;
    memset(vis, 0, sizeof(vis));
    priority_queue<Pair> q; q.push(MP(0, x));
    while(!q.empty()) {
        int p = q.top().se; q.pop();
        if(vis[p]) continue;
        for(int i = head[p]; ~i; i = E[i].nxt) {
            int to = E[i].v;
            if(dis[id][to] > dis[id][p] + E[i].w && (!vis[to])) 
                dis[id][to] = dis[id][p] + E[i].w, q.push(MP(-dis[id][to], to));
        }
    }
}
void Pre() {
    for(int j = 1; j <= 20; j++)
        for(int i = 1; i <= N; i++)
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
}
int lca(int x, int y) {
    if(dep[x] < dep[y]) swap(x, y);
    for(int i = 20; i >= 0; i--)
        if(dep[fa[x][i]] >= dep[y]) x = fa[x][i];
    if(x == y) return x;
    for(int i = 20; i >= 0; i--)
        if(fa[x][i] != fa[y][i])
            x = fa[x][i], y = fa[y][i];
    return fa[x][0];
}
main() {
//    freopen("a.in", "r", stdin);
    memset(head, -1, sizeof(head));
    N = read(); M = read();
    for(int i = 1; i <= M; i++) {
        int x = read(), y = read(), z = read();
        AddEdge(x, y, z);
        AddEdge(y, x, z);
    }
    dfs(1, 0);
    for(int i = 0; i < num; i++) 
        if(!E[i].f) {
            if(!happen[E[i].u]) p.push_back(E[i].u), happen[E[i].u] = 1;
            if(!happen[E[i].v]) p.push_back(E[i].v), happen[E[i].v] = 1;
        }
            
    for(int i = 0; i < p.size(); i++) 
        Dij(p[i], i);
    Pre();
    int Q = read();
    while(Q--) {
        int x = read(), y = read();
        LL ans = Tdis[x] + Tdis[y] - 2 * Tdis[lca(x, y)];
        for(int i = 0; i < p.size(); i++) 
            ans = min(ans, dis[i][x] + dis[i][y]);
        cout << ans << endl;
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏漫漫深度学习路

tensorflow自定义op:梯度

tensorflow自定义op,梯度 tensorflow 是 自动微分的,但是如果你不给它定义微分方程的话,它啥也干不了 在使用 tensorflow 的时...

85270
来自专栏漫漫深度学习路

tensorflow学习笔记(三十三):ExponentialMovingAverage

ExponentialMovingAverage Some training algorithms, such as GradientDescent and M...

56860
来自专栏小樱的经验随笔

Vijos P1131 最小公倍数和最大公约数问题【暴力】

一元三次方程求解 描述 有形如:ax^3+bx^2+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数(a,b,c,d 均为实数),并约定该方程存在三...

34650
来自专栏进击的程序猿

seq2seq模型之raw_rnn

本文是seq2seq模型的第二篇,主要是通过raw_rnn来实现seq2seq模型。 github地址是:https://github.com/zhuanxu...

34320
来自专栏xingoo, 一个梦想做发明家的程序员

在Java Web中使用Spark MLlib训练的模型

模型下载到本地,重新命名为xml。 可以看到默认四个特征分别叫做feild_0,field_1...目标为target

23120
来自专栏owent

POJ PKU 1990 MooFest 解题报告

6310
来自专栏图形学与OpenGL

机械版CG 实验4 裁剪

了解二维图形裁剪的原理(点的裁剪、直线的裁剪、多边形的裁剪),利用VC+OpenGL实现直线的裁剪算法。

19110
来自专栏深度学习之tensorflow实战篇

igraph软件包创建图和网络(创建邻接矩阵)

一、igraph软件包创建图和网络 igraph 是一个独立的库,底层是 C,上层有 Python 和 R 接口,主要做图和网络方面的计算,附带绘图功能。 ...

69540
来自专栏数据结构与算法

1080 线段树练习 单点修改及区间查询

1080 线段树练习 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond 题目描述 Description 一...

30640
来自专栏Jack-Cui

Day4、Python

题目     一个数如果恰好等于它的因子之和,这个数就成为“完数”。例如6=1+2+3。编程找出1000以内的所有完数。 程序分析     完全数(...

26600

扫码关注云+社区

领取腾讯云代金券