题解

Analyssis

​ 题目中涉及到 $n$ 棵树，事实上，我们可以将每棵树看作一个点，存在关系的两棵树之间就有一条无向边相连；如果我们知道这些权值，问题就可以转化为从 $st$ 出发，到 $ed$ 的最短距离，使用 $Dijkstra$ 算法解决即可。

​ 在计算权值时，我们只要知道待合并的结点到根节点的最短路径长度即可。事实上，由于每棵树都为满二叉树，因此我们可以将结点编号二进制化，其对应的二进制数位数 $-1$ 即为我们所求的权值。

Code

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int nnu = 2e5+100;

int Get_weight(int x)
{
    int res=0;
    while(x>1) x>>=1,res++;
    return res;
}

void Dij(vector<vector<int> > &v,vector<vector<int> > &w,int n,int st,int *dist)
{
    for(int i=1;i<=n;i++) dist[i]=1e12;
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> >> q;
    q.push({0,st});dist[st]=0;
    int vis[n+1];
    memset(vis,0,sizeof(vis));
    while(!q.empty())
    {
        pair<int,int> tmp=q.top();q.pop();
        if(vis[tmp.second]) continue;
        vis[tmp.second] = 1;
        for(int i=0;i<v[tmp.second].size();i++)
        {
            if(vis[v[tmp.second][i]]) continue;
            int new_w=w[tmp.second][i]+tmp.first;
            if(new_w<dist[v[tmp.second][i]])
            {
                dist[v[tmp.second][i]]=new_w;
                q.push({new_w,v[tmp.second][i]});
            }
        }
    }
}

signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,m;
    cin>>n>>m;
    vector<vector<int> > v(n+1),w(n+1);
    for(int i=0;i<m;i++)
    {
        int st,ed,tmp1,tmp2;
        cin>>st>>ed>>tmp1>>tmp2;
        v[st].push_back(ed),v[ed].push_back(st);
        w[st].push_back(Get_weight(tmp2)),w[ed].push_back(Get_weight(tmp1));
    }
    int st,ed;
    cin>>st>>ed;
    int dist[n+1];
    Dij(v,w,n,st,dist);
    if(dist[ed]==1e12) cout<<-1<<endl;
    else cout<<dist[ed]<<endl;
    return 0;
}