【 Educational Codeforces Round 51 (Rated for Div. 2) F】The Shortest Statement

【题解】

先处理出来任意一棵树。
然后把不是树上的边处理出来
对于每一条非树边的点(最多21*2个点)
在原图上,做dijkstra
这样就能处理出来这些非树边上的点到其他任意点的最短路了。
然后对于询问x,y
先用LCA+预处理,求出树上的最短路。
接下来考虑有非树边的情况。
显然只要枚举它经过了非树边上的点z
那么用dis[z][x]+dis[z][y]尝试更新ans就好。
只要枚举非树边上的点。
这是突破口。

【代码】

#include <bits/stdc++.h>

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

using namespace std;

const int MAXN = 100000+10;

const int MAX = 17;

vector <int> son[MAXN],w[MAXN];

int n,p[MAXN][MAX+5],dep[MAXN],pre[MAX+5],m;

long long dis[MAXN];

bool vis[MAXN+10];

LL F[45][MAXN];

set<int> myset;

set<pair<LL,int> > q;

void dfs(int x,int f)

{

    vis[x] = true;

    dep[x] = dep[f] + 1;

    p[x][0] = f;

    for (int i = 1; i <= MAX; i++)

        p[x][i] = p[p[x][i - 1]][i - 1];

    int len = son[x].size();

    for (int i = 0; i <= len - 1; i++)

    {

        int y = son[x][i];

        if (y != f)

        {

            if (!vis[y]){

                dis[y] = dis[x] + w[x][i];

                dfs(y, x);

            }else{

                myset.insert(x);myset.insert(y);

            }

        }

    }

}

long long getMinimalDistance(int t0,int t1){

    int pret0 = t0,pret1 = t1;

    if (dep[t0] > dep[t1]) swap(t0, t1);

    for (int i = MAX; i >= 0; i--)

        if (dep[t0] <= dep[t1] - pre[i])

            t1 = p[t1][i];

    if (t1 == t0) return  dis[pret0]+dis[pret1]-2*dis[t0];

    for (int i = MAX; i >= 0; i--)

    {

        if (p[t0][i] == p[t1][i])

            continue;

        t0 = p[t0][i], t1 = p[t1][i];

    }

    return  dis[pret0]+dis[pret1]-2*dis[p[t0][0]];

}

int main()

{

	#ifdef ccy

	    freopen("rush.txt", "r", stdin);

	#endif

    pre[0] = 1;

    for (int i = 1; i <= MAX; i++)

        pre[i] = pre[i - 1] << 1;

    int T;

    T = 1;

    while (T--)

    {

        scanf("%d%d",&n,&m);

        for (int i = 1; i <= n; i++) son[i].clear(),w[i].clear();

        myset.clear();

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

        {

            int x, y, z;

            scanf("%d%d%d",&x,&y,&z);

            son[x].push_back(y);w[x].push_back(z);

            son[y].push_back(x);w[y].push_back(z);

        }

        dis[1] = 0;

        dfs(1, 0);

        int p = 0;

        for (int s:myset){

            p++;

            rep1(i,1,MAXN-1) F[p][i] = -1;

            F[p][s] = 0;

            q.clear();

            q.insert({0,s});

            while (!q.empty()){

                pair<LL,int> temp = (*q.begin());

                q.erase(q.begin());

                int x = temp.second;LL disx = temp.first;

                if (F[p][x]<disx) continue;

                rep1(i,0,(int)son[x].size()-1){

                    int y = son[x][i];LL cost = w[x][i];

                    if (F[p][y]==-1 || F[p][y]>disx+cost){

                        F[p][y] = disx+cost;

                        q.insert({F[p][y],y});

                    }

                }

            }

        }

        int q;

        scanf("%d",&q);

		rep1(i,1,q)

        {

            int t0, t1;

            scanf("%d%d",&t0,&t1);

            long long ans = getMinimalDistance(t0,t1);

            rep1(j,1,p){

                if (F[j][t0]!=-1 && F[j][t1]!=-1){

                    ans = min(ans,F[j][t0]+F[j][t1]);

                }

            }

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

        }

    }

    return 0;

}

巴特西

【 Educational Codeforces Round 51 (Rated for Div. 2) F】The Shortest Statement

最新文章

热门文章