PAT甲级A1072---最短路径

1072 Gas Station (30分)

分析：

先处理加油站的编号问题，把加油站的字母G去掉，然后加上n就是图中加油站的编号。
再遍历所有的加油站，获取到达所有居民房的最短路径。
再按照题目的要求选一个离居民房尽可能远，但不超过范围ds，且平均距离最小的。

C++:

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;


const int maxn = 1020;
const int INF = 1 << 30;

int G[maxn][maxn];
bool isVisit[maxn];
int d[maxn];

int n, m, k, ds;

void dijkstra(int s) {
    fill(isVisit, isVisit + maxn, false);
    fill(d, d + maxn, INF);
    d[s] = 0;
    for (int i = 0; i < m + n; i++) {
        int u = -1, min = INF;
        for (int j = 1; j <= m + n; j++) {
            if (isVisit[j] == false && d[j] < min) {
                min = d[j];
                u = j;
            }
        }
        if (u == -1) {
            return;
        }
        isVisit[u] = true;
        for (int j = 1; j <= m + n; j++) {
            if (isVisit[j] == false && d[u] + G[u][j] < d[j]) {
                d[j] = d[u] + G[u][j];
            }
        }
    }
}

int getId(char str[]) {
    int len = strlen(str);
    int id = 0, product = 1;
    for (int i = len - 1; i >= 0; i--) {
        if (str[i] != 'G') {
            id += (str[i] - '0') * product;
            product *= 10;
        }
    }
    if (str[0] == 'G') {
        return id + n;
    } else {
        return id;
    }
}

int main() {
    scanf("%d%d%d%d", &n, &m, &k, &ds);
    fill(G[0], G[0] + maxn * maxn, INF);
    int a, b, value;
    char city1[5], city2[5];
    for (int i = 0; i < k; i++) {
        scanf("%s %s %d", city1, city2, &value);
        a = getId(city1);
        b = getId(city2);
        G[a][b] = G[b][a] = value;
    }

    double resDis = -1, resAvg = INF;
    int resId = -1;
    for (int i = n + 1; i <= n + m; i++) {
        double minDis = INF, avg = 0;
        dijkstra(i);
        for (int j = 1; j <= n; j++) {
            if (d[j] > ds) {
                minDis = -1;
                break;
            }
            if (d[j] < minDis) {
                minDis = d[j];
            }
            avg += 1.0 * d[j] / n;
        }
        if (minDis == -1) {
            continue;
        }
        if (minDis > resDis) {
            resId = i;
            resDis = minDis;
            resAvg = avg;
        } else if (minDis == resDis && avg < resAvg) {
            resId = i;
            resAvg = avg;
        }
    }
    if (resId == -1) {
        printf("No Solution\n");
    } else {
        printf("G%d\n", resId - n);
        printf("%.1f %.1f\n", resDis, resAvg);
    }
    return 0;
}