1

以 f 个喜欢的农场为起点，跑到其他点的最短路之和

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500;
const int INF = 2147483647;
int p, f, c;
// 喜欢的那些城市
int like[MAXN + 5];
// <终点,权值>
vector<pair<int, int>> e[MAXN + 5];
// dij
int dis[MAXN + 5];
bool vis[MAXN + 5];
priority_queue<pair<int, int>> pq;
// 所有喜欢的城市到城市 i 的距离之和
int sum[MAXN + 5];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> p >> f >> c;
    for (int i = 1; i <= f; i++)
        cin >> like[i];
    for (int i = 1; i <= c; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e[v].push_back({u, w});
        e[u].push_back({v, w});
    }
    for (int i = 1; i <= f; i++)
    {
        int s = like[i];
        for (int i = 1; i <= p; i++)
        {
            dis[i] = INF;
            vis[i] = false;
        }
        dis[s] = 0;
        pq.push({-0, s});
        while (!pq.empty())
        {
            int u = pq.top().second;
            pq.pop();
            if (vis[u])
                continue;
            vis[u] = true;
            for (int i = 0; i < e[u].size(); i++)
            {
                int v = e[u][i].first;
                int w = e[u][i].second;
                if (dis[u] + w < dis[v])
                {
                    dis[v] = dis[u] + w;
                    pq.push({-dis[v], v});
                }
            }
        }
        for (int i = 1; i <= p; i++)
            if (sum[i] != INF && dis[i] != INF)
                sum[i] += dis[i];
            else
                sum[i] = dis[i];
    }
    int ans = 1;
    for (int i = 2; i <= p; i++)
        if (sum[i] < sum[ans])
            ans = i;
    cout << ans << "\n";
    return 0;
}

2

直接多源最短路