算法1

(n*Dijkstra) $O(nmlogn)$

使用堆优化Dijkstra算法求最短路，对每一个节点求一次

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

#define PII pair<int,int>
using namespace std;

const int N = 810,M = 2910;
int h[M],e[M],w[M],ne[M],idx;
int dist[N],cnt[805];
bool st[N];

int n,m,p;

void add(int f,int u,int c){
    ne[idx] = h[f];
    w[idx] = c;
    e[idx] = u;
    h[f] = idx++;
}

int Dijkstra(int start){
    memset(dist,0x3f,sizeof dist);
    memset(st,false,sizeof st);
    dist[start] = 0;
    priority_queue<PII,vector<PII>,greater<PII>>heap;
    heap.push({0,start});

    while(heap.size()){
        PII u = heap.top();
        heap.pop();
        int distance = u.first;
        int v = u.second;

        if(st[v])continue;
        st[v] = true;

        for(int i = h[v];i!=-1;i = ne[i]){
            int j = e[i];
            if(distance + w[i]<dist[j]){
                dist[j] = distance + w[i];
                heap.push({dist[j],j});
            }
        }
    }
    int ans = 0;
    for(int i = 1;i<=n;i++){
        if(dist[i]==0x3f3f3f3f&&cnt[i])return 1e9;
        ans += dist[i]*cnt[i];
    }

    return ans;
}

int main(){
    cin>>p>>n>>m;
    memset(h,-1,sizeof h);

    for(int i = 0;i<p;i++){
        int t;
        cin>>t;
        cnt[t]++;
    }

    for(int i = 0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }

    int res = 1e9;
    for(int i = 1;i<=n;i++)
        res = min(res,Dijkstra(i));


    cout<<res<<endl;

    return 0;
}