题意，给出边和权值，求出两个点间的最短距离。

用离线算法的时候有个地方不知道怎么处理了。在线的本来想用倍增的，但发现倍增算法貌似需要预处理深度而不是权值，不知道怎么处理。套一个rmq的模板吧，用来处理权值的时候。

代码：

#include <cstdio>

#include <cstring>

#include <iostream>

#include <vector>

using namespace std;

const int NN=100010;

int n,m;

vector<pair<int,int> > edge[NN],qe[NN];

vector<int> q1,q2;

int p[NN];

int find(int x)

{

    if (p[x]!=x) p[x]=find(p[x]);

    return p[x];

}

int sum=0,ans[NN],dis[NN];

bool vis[NN]={0};

void lca(int u,int fa)

{

    p[u]=u;

    for (int i=0; i<edge[u].size(); i++)

    {

        int v=edge[u][i].first;

        if (v==fa) continue;

        dis[v]=dis[u]+edge[u][i].second;

        lca(v,u);

        p[v]=u;

    }

    vis[u]=true;

    if (sum==m) return;

    for (int i=0; i<qe[u].size(); i++)

    {

        int v=qe[u][i].first;

        if (vis[v])

            ans[qe[u][i].second]=dis[u]+dis[v]-2*dis[find(v)];

    }

}

int main()

{

    int u,v,w;

    char str[4];

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

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

    {

        edge[i].clear();

    }

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

    {

        scanf("%d%d%d%s",&u,&v,&w,str);

        edge[u].push_back(make_pair(v,w));

        edge[v].push_back(make_pair(u,w));

    }

    scanf("%d",&m);

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

    {

        scanf("%d%d",&u,&v);

        qe[u].push_back(make_pair(v,i));

        qe[v].push_back(make_pair(u,i));

        ans[i]=0;

    }

    dis[1]=0;

    lca(1,0);

    for (int i=0; i<m; i++) printf("%d\n",ans[i]);

    return 0;

}

在线的dfs+rmq模板套一个：

#include <cstdio>

#include <cstring>

#include <iostream>

#include <cmath>

#include <vector>

using namespace std;

const int NN=50000;

int n,rt;

vector<pair<int,int> > edge[NN];

int depth=0;

int bn=0,b[NN*2]; //深度序列

int f[NN*2];          //对应深度序列中的结点编号

int p[NN];             //结点在深度序列中的首位置

int dis[NN];          //结点到根的距离

void dfs(int u,int fa)

{

    int tmp=++depth;

    b[++bn]=tmp; f[tmp]=u; p[u]=bn;

    for (int i=0; i<edge[u].size(); i++)

    {

        int v=edge[u][i].first;

        if (v==fa) continue;

        dis[v]=dis[u]+edge[u][i].second;

        dfs(v,u);

        b[++bn]=tmp;

    }

}

int dp[NN*2][20];

void rmq_init(int n) //以深度序列做rmq

{

    for (int i=1; i<=n; i++) dp[i][0]=b[i];

    int m=floor(log(n*1.0)/log(2.0));

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

      for (int i=1; i<=n-(1<<j)+1; i++)

          dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);

}

int rmq(int l,int r)

{

    int k=floor(log((r-l+1)*1.0)/log(2.0));

    return min(dp[l][k],dp[r-(1<<k)+1][k]);

}

int lca(int a,int b)

{

    if (p[a]>p[b]) swap(a,b);

    int k=rmq(p[a],p[b]);

    return f[k];

}

int main()

{

    int m,u,v,w;

    char str[4];

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

    for (int i=1; i<=n; i++) edge[i].clear();

    while (m--)

    {

        scanf("%d%d%d%s",&u,&v,&w,str);

        edge[u].push_back(make_pair(v,w));

        edge[v].push_back(make_pair(u,w));

    }

    rt=1; dis[rt]=0;

    dfs(1,0);

    rmq_init(bn);

    scanf("%d",&m);

    while (m--)

    {

        scanf("%d%d",&u,&v);

        printf("%d\n",dis[u]+dis[v]-2*dis[lca(u,v)]);

    }

    return 0;

}