[PAT] A1072 Gas Station

最短路径

题目大意

从m个加油站里面选取1个站点，让它和离它最近的居民区距离最远，并且没有超出服务范围ds之内。如果有很多个最远的加油站，输出距离所有居民区距离平均距离最小的那个。如果平均值还是一样，就输出加油站编号最小的那个。

思路

Dijkstra算法。注意每次调用Dijkstra都要初始化。
因为加油站之间也是彼此有路连接的，所以最短路径计算的时候也要把加油站算上。因此考虑将加油站和居民点放在一起，用Dijkstra时循环的范围时1~n+m。可以根据输入的是G还是数字来判断，如果是数字就令编号为他自己，如果是G开头的，编号设为n+G后面的数字。
我是先针对每个加油站调用一次Dijkstra，将满足可连通、没有超出服务范围的所有加油站及各项参数（最近点的距离、平均距离、加油站编号）存在另一个结构体中，再统一判断求最优解。（因为数据量<=10,我就直接图方便写了个排序。最近点距离较远->平均距离较短->加油站编号较小）

坑

坑点集中在最后一个测试点4：
（1）加油站和居民点的输入按照string，然后转成数字时要注意它不仅是1位数，可能是多位数。（str.erase(str.begin()+x);中参数是迭代器！）
（2）.1f%的输出会自动四舍五入，不用+0.05。

AC代码

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
#define N 1020
#define INF 100000000
struct way {
    double dis, min;
    int index;
}ways[12];
int numways = 0;
struct node {
    int v, distance;
};
vector<node>Adj[N];
int n, m;//1~n是居民点；n+1~n+m是加油站
int dis[N];
bool vis[N] = { false };
void Dijkstra(int s) {
    int i, j;
    for (i = 0;i < N;i++) {
        dis[i] = INF;
        vis[i] = false;
    }
    dis[s] = 0;
    for (i = 0;i < n + m;i++) {
        int min = INF, u = -1;
        for (j = 1;j <= n + m;j++) {
            if (min > dis[j] && vis[j] == false) {
                min = dis[j];
                u = j;
            }
        }
        if (u == -1)return;
        vis[u] = true;
        for (j = 0;j < Adj[u].size();j++) {
            int v = Adj[u][j].v;
            if (vis[v] == false && dis[v] > dis[u] + Adj[u][j].distance) {
                dis[v] = dis[u] + Adj[u][j].distance;
            }
        }
    }
}
bool cmp(way a, way b) {
    if (a.min != b.min)return a.min > b.min;
    else if (a.dis != b.dis)return a.dis < b.dis;
    else return a.index < b.index;
}
int strtoint(string a) {
    int ans = 0;
    for (int i = 0;i < a.size();i++)
        ans = ans * 10 + a[i] - '0';
    return ans;
}
int main() {
    int i, j, k, dmax;
    scanf("%d%d%d%d", &n, &m, &k, &dmax);
    for (i = 0;i < k;i++) {
        int p1, p2, dist;
        string s_p1, s_p2;
        cin >> s_p1 >> s_p2 >> dist;      
        if (s_p1[0] == 'G') {
            s_p1.erase(s_p1.begin());
            p1 = strtoint(s_p1) + n;
        }
        else p1 = strtoint(s_p1);
        if (s_p2[0] == 'G') {
            s_p2.erase(s_p2.begin());
            p2 = strtoint(s_p2) + n;
        }
        else p2 = strtoint(s_p2);
        node temp;
        temp.distance = dist;
        temp.v = p1;Adj[p2].push_back(temp);
        temp.v = p2;Adj[p1].push_back(temp);
    }
    for (i = n + m;i > n;i--) {
        Dijkstra(i);
        for (j = 1;j <= n;j++)
            if (dis[j] > dmax)break;
        if (j == n + 1) {//符合条件的路径存在
            ways[numways].index = i - n;
            int dmin = INF;
            for (k = 1;k <= n;k++) {//计算总路径长和最小路径值
                if (dmin > dis[k])dmin = dis[k];
                ways[numways].dis += dis[k];
            }
            ways[numways].min = dmin;
            ways[numways].dis = ways[numways].dis / n;
            numways++;
        }
    }
    if (numways == 0)printf("No Solution\n");
    else {
        sort(ways, ways + numways, cmp);//顺手写了个排序，其实duck不必。找最小值就好了~
        printf("G%d\n%.1f %.1f\n", ways[0].index, ways[0].min, ways[0].dis);
    }
    return 0;
}