题目链接： https://acm.uestc.edu.cn/problem/oydyde-zheng-tu-iii/description

分析：

这道题一开始没看懂题意，在cla里问了一下。

搞清楚题意后，那么显然，这是在求两点之间的最短距离。

任意两点最短距离的Floyd-Warshall算法复杂度O(N^3)，显然不可能。

强行跑Dijkstra，不出所料的在11点TLE了。然后试了一下离线所有询问，排序后再跑Dijkstra，还是过不去。

认真观察题目，注意到边的数目非常小，极限情况下是一条长链。联想到数据结构B题，极限情况也是长链，而且notes里写着“你以为我是图论，其实我是数据结构”。

然后搜索了一下最短路+LCA，找到了题意类似的。

先跑一个生成树出来，是不是最小没关系。然后LCA倍增求出两点的距离。接着在那些没使用的边的两个端点上跑最短路，出题人说只用跑一个点，这个我倒是没想到。

路径分为只走树上的边，和走了未使用的边两种情况。所以我们只需要在未使用的边的两个端点跑最短路。d[u]+d[v]即是这个点到两个询问点的最短距离。

极限情况是一个LCA加60个最短路，无脑取min即可。

总的复杂度就是LCA预处理加上多次Dijkstra的复杂度。

代码：

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
using namespace std;
const long long INF = 1ll << 60;

///////////////////////////
const long long MAXV=100050;
long long used[MAXV];

vector<long long> unused;
long long father[MAXV][20];
long long depth[MAXV];
long long lca_d[MAXV];

struct edge
{
    long long to,cost;
};
long long V;
vector<edge> G[MAXV];
long long d[100][MAXV];

//////////////
void dfs(long long v,long long _father,long long _cost,long long dp)
{
	father[v][0] = _father; lca_d[v]=_cost;depth[v] = dp;++used[v];
	long long len = G[v].size();
	for (long long i = 0; i < len; i++)
	{
		if (G[v][i].to != _father)
		{
		    if(used[G[v][i].to] == 0)
            {
                dfs(G[v][i].to, v, lca_d[v]+G[v][i].cost, dp+1);
            }
		    else
            {
                unused.push_back(v);
                unused.push_back(G[v][i].to);
            }
		}
	}
}
void lca_init()
{
    dfs(1,0,0,1);
	for (long long k = 1; k < 20; ++k)
	{
		for (long long i = 1; i <= V; i++)
		{
			father[i][k] = father[father[i][k - 1]][k - 1];
		}
	}
}
long long lca(long long a,long long b)
{
    if (a == b)return father[a][0];
    if (depth[a] > depth[b])swap(a, b);
    for (long long k = 19; depth[b] > depth[a]; --k)
    {
        if ((depth[b] - depth[a]) >> k & 1)
        {
            b = father[b][k];
        }
    }
    if (a != b)
    {
        for (long long k = 19; k >= 0; --k)
        {
            if (father[a][k] != father[b][k])
            {
                a = father[a][k];
                b = father[b][k];
            }
        }
        return father[a][0];
    }
    else
    {
        return a;
    }
}
///////////


void dijkstra(long long s,long long id)
{
    priority_queue< pair<long long,long long> , vector< pair<long long,long long> > ,greater< pair<long long,long long> > > q;
    fill(d[id],d[id]+V+1,INF);
    d[id][s]=0;
    q.push( pair<long long,long long>(0,s) );
    while(!q.empty())
    {
        pair<long long,long long> p=q.top();
        q.pop();
        long long v=p.second;
        if(d[id][v]<p.first)
            continue;
        long long len=G[v].size();
        for(long long i=0;i<len;++i)
        {
            edge e=G[v][i];
            if(d[id][e.to] > d[id][v] + e.cost)
            {
                d[id][e.to] = d[id][v] + e.cost;
                q.push(pair<long long,long long>(d[id][e.to],e.to));
            }
        }
    }
}

////////

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    memset(used,0,sizeof(used));
    lca_d[0]=0;
    long long m,u,v,w;
    cin>>V>>m;
    for(long long i=0;i<m;++i)
    {
        cin>>u>>v>>w;
        G[u].push_back((edge){v,w});
        G[v].push_back((edge){u,w});
    }
    lca_init();
    sort(unused.begin(),unused.end());
    long long len=unique(unused.begin(),unused.end()) - unused.begin();
    for(long long i=0;i<len;++i)
    {
        dijkstra(unused[i],i);
    }
    long long t,sum=0,last=1,ans,linshi;
    cin>>t;
    for(long long i=0;i<t;++i)
    {
        cin>>linshi;
        ans=lca_d[last]+lca_d[linshi]-2*lca_d[lca(last,linshi)];
        for(long long j=0;j<len;++j)
        {
            ans=min(d[j][last]+d[j][linshi],ans);
        }
        sum+=ans;
        last=linshi;
    }
    cout<<sum<<endl;
    return 0;
}