Gas Station

链接：https://www.nowcoder.com/questionTerminal/aba54c5142454a4f830b3eb93dd71d3a
来源：牛客网
转载大佬的。
这题一开始我根本没理解题意（难受），后来才发现是让house到station的最短距离达到最大，然后在根据平均距离排序。还有坑的地方在于牛客输入数据会有重复边，遇到重复时要选最小的边权。然后，理解 了题意后还是好写的，就是坑太多。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+20;
const int INF=0x3f3f3f3f;
int n,m,k,Ds,G[maxn][maxn],dis[maxn];//1~n:house n+1~n+m:station
bool visit[maxn];
 
int getId(string &s){
    if(s[0]=='G'){
        if(s.size()==2) return n+s[1]-'0';
        else return n+10;
    }else{
        return stoi(s);
    }
}
//最短路径
void dijkstra(int s,int N){
    fill(dis,dis+N+1,INF);
    fill(visit,visit+N+1,0);
    dis[s]=0;
    for(int i=1;i<=N;i++){
        int u=-1,min=INF;
        for(int j=1;j<=N;j++){
            if(!visit[j] && dis[j]<min){
                min=dis[j];
                u=j;
            }
        }
        if(u==-1) return;
        visit[u]=true;
        for(int v=1;v<=N;v++){
            if(!visit[v] && G[u][v]!=0){
                int tempDis=dis[u]+G[u][v];
                if(tempDis<dis[v]){
                    dis[v]=tempDis;
                }
            }
        }
    }
}
int main()
{   
    fill(G[0],G[0]+maxn*maxn,INF);
    cin>>n>>m>>k>>Ds;
    string p1,p2;
    int a,b,c;
    for(int i=0;i<k;i++){
        cin>>p1>>p2>>c;
        a=getId(p1);
        b=getId(p2);
        G[a][b]=G[b][a]=min(c,G[a][b]);
    }
    int choice=-1;
    double minDis=-INF,meanDis,tempMindis,tempMeandis;
    for(int i=n+1;i<=n+m;i++){
        dijkstra(i,n+m);
        if(*max_element(dis+1,dis+n+1)>Ds) continue;//存在dis>Ds
        tempMindis=*min_element(dis+1,dis+n+1);
        tempMeandis=accumulate(dis+1,dis+n+1,0)*1.0/n;
        //比较不同出发点，house到station的最短距离
        if(tempMindis>minDis){
            minDis=tempMindis;
            meanDis=tempMeandis;
            choice=i-n;
        }else if(tempMindis==minDis){
            if(tempMeandis<meanDis){
                meanDis=tempMeandis;
                choice=i-n;                
            }
        }
    }
    if(choice!=-1){
        cout<<"G"<<choice<<endl;
        printf("%.1f %.1f",minDis,meanDis);
    }else{
        cout<<"No Solution";
    }
    return 0;
}