个人练习-PAT甲级-1072 Gas Station

题目链接https://pintia.cn/problem-sets/994805342720868352/problems/994805396953219072

死亡冲锋hhh
好久没做图论的题了，感觉图论一般就是考Dijkstra，拓扑排序和最小生成树。这题看上去应该就是Dijkstra，但是因为好久没写，得翻着书才能写出来。。。

题目给出N个居民点，M个加油站候选点，然后给出他们之间的路径长度，求一个合适的候选站点：他离最近居民点的距离尽可能大，并且离所有居民点距离小于等于Ds。如果答案不唯一，再按照平均距离和编号进行排序。

完整代码

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<stdio.h>
#include<math.h>
#include<map>
#include<set>
#include<queue>
#include<string.h>using namespace std;const int MAXN = 1100;
const int MAXD = 999999999;class Gast {
    
public:int idx;double min_dis, avg_dis;
};int g[MAXN][MAXN];
int N, M, K, Ds, T;
bool known[MAXN];
int dist[MAXN];void Init() {
    for (int i = 1; i <= T; i++) {
    for (int j = 1; j <= T; j++) {
    if (i != j)g[i][j] = MAXD;}}
}int getLoc(char p[]) {
    int len = strlen(p);int ret = 0;if (p[0] == 'G') {
    for (int i = 1; i < len; i++) {
    ret *= 10;ret += (p[i] - '0');}return ret + N;}      else {
    for (int i = 0; i < len; i++) {
    ret *= 10;ret += (p[i] - '0');}return ret;}
}void Reset() {
    for (int i = 1; i <= T; i++) {
    known[i] = false;dist[i] = MAXD;}
}void Dijkstra(int s) {
    int v;for (int i = 1; i < T; i++)dist[i] = g[s][i];while (1) {
    v = 0;int min_dis = MAXD;for (int i = 1; i <= T; i++) {
    if (!known[i] && dist[i] < min_dis) {
    min_dis = dist[i];v = i;}}if (v == 0)break;known[v] = true;for (int w = 1; w <= T; w++) {
    if (!known[w]) {
    if (dist[v] + g[v][w] < dist[w])dist[w] = dist[v] + g[v][w];                               }}}
}bool cmp(Gast x, Gast y) {
    if (x.min_dis != y.min_dis)return x.min_dis > y.min_dis;else {
    if (x.avg_dis != y.avg_dis)return x.avg_dis < y.avg_dis;elsereturn x.idx < y.idx;}}int main() {
    bool flag = true;scanf("%d %d %d %d", &N, &M, &K, &Ds);T = N + M;Init();for (int i = 0; i < K; i++) {
    char p1[4], p2[4];int tmp_dis, loc1, loc2;scanf("%s %s %d", p1, p2, &tmp_dis);loc1 = getLoc(p1);loc2 = getLoc(p2);g[loc1][loc2] = min(g[loc1][loc2], tmp_dis);g[loc2][loc1] = g[loc1][loc2];}Gast ans;ans.min_dis = -1;ans.idx = 0;ans.avg_dis = MAXD;for (int s = N + 1; s <= T; s++) {
    Reset();Dijkstra(s);Gast tmp_sta;tmp_sta.avg_dis = 0.0;tmp_sta.min_dis = 1.0 * MAXD;bool flag = true;for (int j = 1; j <= N; j++) {
    if (dist[j] <= Ds) {
    tmp_sta.avg_dis += 1.0 * dist[j];if (dist[j] < tmp_sta.min_dis)tmp_sta.min_dis = dist[j];}else {
    flag = false;break;}}if (flag) {
    tmp_sta.idx = s;tmp_sta.avg_dis /= (1.0 * N);if (cmp(tmp_sta, ans)) {
    ans.avg_dis = tmp_sta.avg_dis;ans.min_dis = tmp_sta.min_dis;ans.idx = tmp_sta.idx;}}}if (ans.min_dis < 0)printf("No Solution");elseprintf("G%d\n%.1f %.1f", ans.idx - N, ans.min_dis, ans.avg_dis);return 0;
}

思路：先读入数据，注意M有可能是两位数，因此char[]要至少给4位，测试点4测的就是这里。

    for (int i = 0; i < K; i++) {
    char p1[4], p2[4];int tmp_dis, loc1, loc2;scanf("%s %s %d", p1, p2, &tmp_dis);loc1 = getLoc(p1);loc2 = getLoc(p2);g[loc1][loc2] = min(g[loc1][loc2], tmp_dis);g[loc2][loc1] = g[loc1][loc2];}

然后对每一个候选点Dijkstra，得到他离所有居民点的距离（都已经是最短的）。注意每次Dijkstra之前要做一些对辅助数组dist[],known[]的初始化处理，详见Reset()函数。

然后遍历一遍得到其中的最小值，存入tmp_sta.min_dis里。若离某一个居民点距离大于Ds了，就让flag为false，说明这个候选点根本不满足条件，不用考虑了。若都满足，就和ans比较，比较条件见cmp()函数。因为只要得出min_dis最大的一个候选点即可，因此不需要对所有满足条件的候选点排序，不然会超时的。

for (int s = N + 1; s <= T; s++) {
    Reset();Dijkstra(s);Gast tmp_sta;tmp_sta.avg_dis = 0.0;tmp_sta.min_dis = 1.0 * MAXD;bool flag = true;for (int j = 1; j <= N; j++) {
    if (dist[j] <= Ds) {
    tmp_sta.avg_dis += 1.0 * dist[j];if (dist[j] < tmp_sta.min_dis)tmp_sta.min_dis = dist[j];}else {
    flag = false;break;}}if (flag) {
    tmp_sta.idx = s;tmp_sta.avg_dis /= (1.0 * N);if (cmp(tmp_sta, ans)) {
    ans.avg_dis = tmp_sta.avg_dis;ans.min_dis = tmp_sta.min_dis;ans.idx = tmp_sta.idx;}}}