直接floyd会超时

#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <stack>
#include <vector>
#include <queue>
#include <deque>
#include <cstring>

using namespace std;


const int N = 900; // 


int n,p,c;

int dist[N][N];
int pt[1000];

void floyd()
{

    for(int i=1;i<=p;i++)
    {
        for(int j=1;j<=p;j++)
        {
            for(int k=1;k<=p;k++)
            {
                dist[j][k]=min(dist[j][k],dist[j][i]+dist[i][k]);
            }
        }
    }
}

int main()
{
    cin>>n>>p>>c;
    memset(dist,0x3f,sizeof dist);
    for(int i=1;i<=n;i++)
    {
        int cow;
        cin>>cow;
        pt[cow]++;
    }
    for(int i=1;i<=c;i++)
    {
        int x,y,w;
        cin>>x>>y>>w;
        dist[x][y]=min(dist[x][y],w);
        dist[y][x]=min(dist[y][x],w);
    }
    for(int i=1;i<=p;i++)
    {
        dist[i][i]=0;
    }
    floyd();
    int cost=0x3f3f3f3f;
    //遍历p个牧场,把每个牧场作为起点
    for(int i=1;i<=p;i++)
    {
        int pc=0;
        for(int j=1;j<=p;j++)
        {
            pc=pc+pt[j]*dist[i][j];
            //cout<<i<<" "<<j<<" "<<dist[i][j]<<endl;
        }
        cost = min(cost,pc);
    }
    cout<<cost;
    return 0;
}

堆优化的djk顺利ac了，注意要用long long

#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <stack>
#include <vector>
#include <queue>
#include <deque>
#include <cstring>

using namespace std;


typedef pair<int, int> PII;
const int N = 150010; // 


int n,p,c;
int pt[1000];
int h[N], e[N], ne[N], idx;
int w[N]; // 用来存权重
int dist[N];
int st[N]; // 如果为true说明这个点的最短路径已经确定

priority_queue<PII, vector<PII>, greater<PII>> heap;

void add(int a,int b,int c)
{
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}
void djk(int start)
{
    memset(dist,0x3f,sizeof dist);
    memset(st,0,sizeof st);
    dist[start]=0;
    //st[1]=1;
    heap.push({0,start});
    while(heap.size())
    {
        auto t=heap.top();
        heap.pop();

        int ver=t.second;
        int ds=t.first;

        if(st[ver])
        continue;

        st[ver]=1;
        for(int i=h[ver];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>ds+w[i])
            {
                dist[j]=ds+w[i];
                heap.push({dist[j],j});

            }

        }
    }

}


int main()
{
    cin>>n>>p>>c;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++)
    {
        int cow;
        cin>>cow;
        pt[cow]++;
    }
    for(int i=1;i<=c;i++)
    {
        int a,b,w;
        cin>>a>>b>>w;
        add(a,b,w);
        add(b,a,w);
    }
    int cost=0x3f3f3f3f;
    for(int i=1;i<=p;i++)
    {
        long long pc=0;
        djk(i);
        for(int j=1;j<=p;j++)
        {
            pc=pc+pt[j]*dist[j];
            //cout<<i<<" "<<j<<" "<<dist[i][j]<<endl;
        }
        cost = min((long long)cost,pc);
    }
    cout<<cost;

    return 0;
}

三刷，顺利

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>

using namespace std;

const int N=100010;
int e[N],ne[N],h[N],w[N],dist[N],st[N],idx;

typedef pair<int,int> pii;
priority_queue<pii,vector<pii>,greater<pii>> heap;

int n,m,cow[N],c;

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

void djk(int s)
{
    memset(dist,0x3f,sizeof dist);
    memset(st,0,sizeof st);
    dist[s]=0;
    heap.push({0,s});

    while(heap.size())
    {
        auto t=heap.top();
        heap.pop();
        int u=t.second;
        int d=t.first;

        if(st[u]) continue;
        st[u]=1;

        for(int i=h[u];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[u]+w[i])
            {
                dist[j]=dist[u]+w[i];
                heap.push({dist[j],j});
            }
        }
    }

}


int main()
{
    cin>>c>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=1;i<=c;i++) cin>>cow[i];
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }

    long long res=0x3f3f3f3f;
    long long ans;
    for(int i=1;i<=n;i++)
    {
        ans=0;
        djk(i);
        for(int j=1;j<=c;j++)
        {
            ans+=dist[cow[j]];
        }
        res=min(res,ans);
    }

    cout<<res;
    return 0;
}

2023//12/2

没什么问题，注意数据范围，数组要开大
```#include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

typedef pair[HTML_REMOVED] PII;
const int N = 10010;
int n,m,p;
int e[N],ne[N],h[N],w[N],idx;
int st[N],dist[N];
int farm[N];

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

long long djk(int start)
{
memset(st, 0, sizeof(st));
memset(dist, 0x3f, sizeof(dist));

priority_queue<PII, vector<PII>, greater<PII>> heap;

dist[start] = 0;
heap.push({0, start});

while(heap.size())
{
    auto t =heap.top();
    heap.pop();

    int var = t.second;
    int d=t.first;

    if(st[var]) continue;
    st[var] = 1;

    for(int i=h[var];i!=-1;i=ne[i])
    {
        int j=e[i];

        if(dist[j] > d+w[i])
        {
            dist[j] = d+w[i];
            heap.push({dist[j], j});
        }
    }
}

long long res=0;
for(int i=1;i<=p;i++)
{
    res += dist[farm[i]];
}

return res;

}

int main()
{
memset(h, -1, sizeof(h));
cin>>p>>n>>m;
for(int i=1;i<=p;i++)
{
cin>>farm[i];
}

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

long long res=0x3f3f3f3f;
for(int i=1;i<=n;i++)
{
    res = min(res, djk(i));
}

cout<<res;


return 0;

}

```