跳至正文

1 条题解

  • 0
    @ 2026-10-2 2:21:55

    从每个候选牧场计算最短距离,重边保留最短权值,不累加不可达距离;距离和使用long long。

    #include <bits/stdc++.h>
    using namespace std;
    
    int main(){ios::sync_with_stdio(false);cin.tie(nullptr);
    
    int n,p,m;cin>>n>>p>>m;vector<int>count(p);for(int i=0;i<n;i++){int x;cin>>x;count[x-1]++;}vector<vector<pair<int,int>>>graph(p);while(m--){int a,b,w;cin>>a>>b>>w;--a;--b;graph[a].push_back({b,w});graph[b].push_back({a,w});}const long long INF=LLONG_MAX/8;long long answer=INF;for(int start=0;start<p;start++){vector<long long>d(p,INF);d[start]=0;priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>>q;q.push({0,start});while(!q.empty()){auto[distance,u]=q.top();q.pop();if(distance!=d[u])continue;for(auto[v,w]:graph[u])if(distance+w<d[v]){d[v]=distance+w;q.push({d[v],v});}}long long sum=0;bool possible=true;for(int i=0;i<p;i++)if(count[i]){if(d[i]==INF){possible=false;break;}sum+=count[i]*d[i];}if(possible)answer=min(answer,sum);}cout<<answer<<"\n";
    
    return 0;
    }
    
    • 1

    信息

    ID
    4020
    时间
    1000ms
    内存
    128MiB
    难度
    5
    标签
    递交数
    0
    已通过
    0
    上传者