问题描述

测试数据大部分过去了，但是下面这组不能过
3 5 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5

发现是有些牧场没和别的地方联通，如果还对这个牧场进行djst的话就有问题了，所以弄一个able[]记录那些牧场可以去尝试

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
#include<functional>
using namespace std;
typedef pair<int, int> PII;
const int N = 5000;
int e[N], ne[N], h[N], w[N];
int dist[N], num[N],able[N];//距离，牧场奶牛数目,能否选择这个牧场
bool vist[N];
int n, p, t, idx;
int a, b, c;//临时变量

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

int djst(int s){
    memset(dist, 0x3f, sizeof dist);
    memset(vist, false, sizeof vist);
    dist[s] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> q;
    q.push({ 0, s });
    while (q.size()){
        int ver = q.top().second, distence = q.top().first;
        q.pop();
        if (vist[ver]) continue;
        vist[ver] = true;
        for (int i = h[ver]; i != -1; i = ne[i]){
            int j = e[i], z = w[i];
            if (dist[j] > dist[ver] + z){
                dist[j] = dist[ver] + z;
                q.push({ dist[j], j });
            }
        }
    }
    int res = 0;
    for (int i = 1; i <= p; i++)
        res += num[i] * dist[i];
    return res;
}


int main(void){
    cin >> n >> p >> t;
    memset(h, -1, sizeof h);
    while (n--){
        cin >> a;
        num[a]++;
    }

    while (t--){
        cin >> a >> b >> c;
        able[a]++;
        able[b]++;
        add(a, b, c);
        add(b, a, c);
    }
    int ans = 0x3f3f3f3f;
    for (int i = 1; i <= p && able[i] !=0; i++){
        ans=min(ans,djst(i));
    }
    cout<<ans<<endl;
    return 0;
}