PAT甲级1072Gas Station

Posted on | | Visitors:
Words count in article: 881 字 | Reading time ≈ 4 分

题目链接

https://pintia.cn/problem-sets/994805342720868352/problems/994805396953219072

题解

题目要求

加油站要离各个住宅的最小距离应该尽可能地大，但也要保证住宅在加油区的服务距离内。

现在给出几个加油站的候选位置，请你找出最好的一个（距离各住宅的最小距离最大）。如果有多个解，则选择离住宅平均距离最短的那个。如果还是有多个解，则选择索引较小的那个。

  • 输入

    • N：正整数，不超过1000，住宅的数量，住宅索引为[1,N]
    • M：正整数，不超过10，加油站候选位置的数量，索引为[G1,GM]
    • K：正整数，不超过10000，边的数量
    • Ds：正整数，加油站的最大服务距离
    • K条边

  • 输出

    • 加油站候选位置的索引

    • 加油站与住宅的最短距离和平均距离

      数字必须精确到小数点后一位。

    • 解不存在则输出No Solution

解题思路

除了输入输出需要懂点心思，这道题就是一道简单的单源最短路题目了。

  • 这里有两类结点：住宅和加油站，可以对输入进行处理，规定索引[1,n]是住宅，索引[n+1,n+m]是加油站
  • 然后对每个加油站运行dijkstra算法，在不超过加油站服务距离的前提下求解
  • 注意是优先求距离各住宅的最小距离最大的解

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
// Problem: PAT Advanced 1072
// URL: https://pintia.cn/problem-sets/994805342720868352/problems/994805396953219072
// Tags: 图 最短路 单源最短路 dijkstra BFS

#include <iostream>
#include <climits>
#include <string>
#include <vector>
using namespace std;

const int INF = INT_MAX;
const int MAXN = 1011; // [1,n]是住宅，[n+1,n+m]是加油站
int n, m, k, ds;
bool visited[MAXN]; 
int dis[MAXN][MAXN];
int minDis[MAXN];


int main()
{
    fill(dis[0], dis[0] + MAXN * MAXN, INF);
    for (int i = 0; i < MAXN; i++)
        dis[i][i] = 0;

    scanf("%d %d %d %d", &n, &m, &k, &ds);
    string aStr, bStr;
    int a, b, c;
    for (int i = 0; i < k; i++){
        cin >> aStr >> bStr;
        a = (aStr[0] == 'G') ? stoi(aStr.substr(1)) + n : stoi(aStr);
        b = (bStr[0] == 'G') ? stoi(bStr.substr(1)) + n : stoi(bStr);
        scanf("%d", &c);
        if (c < dis[a][b]) // 处理输入的特殊情况
            dis[a][b] = dis[b][a] = c;
    }

    // 对每个加油站运行dijkstra算法
    int ansStation = -1;
    double ansDis = -INF, ansAverDis = INF;
    for (int station = n + 1; station <= n + m; station++){
        double tempMin = INF, averDis = 0;

        fill(minDis, minDis + MAXN, INF);
        fill(visited, visited + MAXN, false);

        // 运行dijkstra算法，求该加油站到其它加油站和住宅的最短路径
        minDis[station] = 0;
        for (int i = 1; i <= n + m; i++){
            int tempMin = INF, u = -1;
            for (int j = 1; j <= n + m; j++){
                if (!visited[j] && minDis[j] < tempMin){
                    u = j;
                    tempMin = minDis[j];
                }
            }
            if (u == -1) break;
            visited[u] = true;
            for (int v = 1; v <= n + m; v++){
                if (!visited[v] && dis[u][v] != INF){
                    if (minDis[v] > minDis[u] + dis[u][v]){
                        minDis[v] = minDis[u] + dis[u][v];
                    }
                }
            }
        }

        // 更新最终结果
        for (int i = 1; i <= n; i++){
            if (minDis[i] > ds){
                tempMin = -1;
                break;
            }
            if (minDis[i] < tempMin){
                tempMin = minDis[i];
            }
            averDis += minDis[i];
        }

        if (tempMin == -1) continue;
        averDis /= n;
        if (tempMin > ansDis){
            ansDis = tempMin;
            ansStation = station;
            ansAverDis = averDis;
        }
        else if (tempMin == ansDis && averDis < ansAverDis){
            ansStation = station;
            ansAverDis = averDis;
        }
    }

    if (ansStation == -1)
        printf("No Solution");
    else
        printf("G%d\n%.1f %.1f", ansStation - n, ansDis, ansAverDis);

    return 0;
}

作者：@臭咸鱼

转载请注明出处：https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!