2021-04-06 PAT A1072

测试点3坑了我3个小时。。。。。
因为他的最短距离就是最远的服务范围

#include<cstdio>
#include<cstring>
#include<vector>
#include<utility>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn = 1020, INF = 0x3fffffff;
int n, m, k, DS, dis[maxn];//index代表的是候选位置插入的编号
bool vis[maxn];
vector<pair<int, int> > graph[maxn];//第一个项是ID，第二个是距离
int getID(char* name) {
    if (name[0] == 'G') {
        int len = strlen(name);
        for (int i = 0; i < len; i++)name[i] = name[i + 1];
        return n + atoi(name);
    }
    return atoi(name);
}
int main() {
    scanf("%d %d %d %d", &n, &m, &k, &DS); getchar();
    for (int i = 0; i < k; i++) {
        char name_A[6], name_B[6]; int w;
        scanf("%s %s %d", name_A, name_B, &w);getchar();
        int A_ID = getID(name_A), B_ID = getID(name_B);
        graph[A_ID].push_back(pair<int, int>(B_ID, w));
        graph[B_ID].push_back(pair<int, int>(A_ID, w));
    }
    float averagedis = 999999999.0;
    int length = -1,  code = -1;//用来记录最大的最短距离
    for (int i = n + 1; i <= n + m; i++) {//使用dij
        priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
        memset(vis, 0, sizeof vis);
        fill(dis, dis + maxn, INF);
        q.push(pair<int, int>(0, i)); dis[i] = 0;
        for (int j = 0; j < n + m; j++) {//因为其中有n + m个点，要让每个点都松弛到，所以要松弛n + m 次
            if (q.empty())break;
            pair<int, int> temp = q.top(); q.pop(); vis[temp.second] = true;
            int u = temp.second;
            for (int k = 0; k < graph[u].size(); k++) {
                int  v = graph[u][k].first, w = graph[u][k].second;
                if (!vis[v] && dis[u] + w < dis[v]) {
                    dis[v] = dis[u] + w;
                    //vis[v] = true;只有弹栈的时候才停止，没有弹栈之前，他都有被松弛的可能
                    q.push(pair<int, int>(dis[v],v));
                }
            }
        }
        int temp_length = INF;
        double temp_average = 0.0;
        for (int j = 1; j <= n; j++) { 
            if ( dis[j] > DS) { temp_length = dis[j]; break;} 
            if (dis[j] < temp_length)temp_length = dis[j];//找到距离加油站最近的距离
            temp_average += (double) dis[j]; 
        }
        if (temp_length <= DS) {
            temp_average /= (double) n;//求出平均距离
            if (temp_length > length) {
                code = i;//记下最合适的加油站
                length = temp_length;
                averagedis = temp_average;
            }
            else if (temp_length == length && temp_average < averagedis) {
                code = i;//记下最合适的加油站
                averagedis = temp_average;
            }
        }
    }
    if (code == -1) printf("No Solution\n");
    else printf("G%d\n%.01f %.01f\n", code - n, (double)length, averagedis);
    return 0;
}