[C++知识库]L3-005 垃圾箱分布 (30 分)（dijkstar

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+9;
int dist[N],vis[N];

struct node {
    int to,w;
};
vector<node>v[N];
typedef pair<int,int> pii;
void dij(int st){
    priority_queue<pii,vector<pii>,greater<pii>>q;
    memset(dist,0x3f,sizeof dist);
    memset(vis,0,sizeof vis);
    dist[st]=0;
    q.push({0,st});
    while(q.size()){
        auto p=q.top();
        q.pop();
        if(vis[p.second])continue;
        vis[p.second]=1;
        for(auto it:v[p.second]){
            if(dist[it.to]>dist[p.second]+it.w){
                dist[it.to]=dist[p.second]+it.w;
                q.push({dist[it.to],it.to});
            }
        }
    }

}

int main(){
    int n,m,k,ds;
    cin>>n>>m>>k>>ds;
    while(k--){
        string A,B;
        int c;
        cin>>A>>B>>c;
        int a,b;
        if(isdigit(A[0]))a=atoi(A.c_str());
        else a=atoi(A.substr(1).c_str())+1000;
        if(isdigit(B[0]))b=atoi(B.c_str());
        else b=atoi(B.substr(1).c_str())+1000;
         v[a].push_back({b,c});
        v[b].push_back({a,c});
        // cout<<A<<" "<<B<<"\n";
        // cout<<a<<" "<<b<<" "<<c<<"\n";
    }
    double ansmi=0,ansavg=0x3f3f3f3f,ansid=-1;
    for(int i=1;i<=m;i++){
        dij(i+1000);
        int ok=1;
        double sum=0;
        int mi=0x3f3f3f3f;
        for(int j=1;j<=n;j++){
            if(dist[j]>ds){
                ok=0;
                break;
            }
            else sum+=dist[j];
            mi=min(mi,dist[j]);
        }
        if(ok){
            sum=sum*1.0/n;
            if(mi>ansmi){
                ansid=i;
                ansmi=mi;
                ansavg=sum;
            }
            else if(mi==ansmi&&sum<ansavg){
                ansid=i;
                ansmi=mi;
                ansavg=sum;
            }
            // cout<<i<<"---\n";
            // cout<<mi<<" "<<sum<<"\n";
        }
    }
    // cout<<ansid<<"\n";
    if(ansid!=-1)
    cout<<"G"<<ansid<<"\n",printf("%.01lf %.01lf",ansmi,ansavg);
    else cout<<"No Solution\n";
    return 0;
}

阅读世界，共赴山海

423全民读书节，邀你共读