PTA A_1072 Gas Station

798236606

传送门：https://pintia.cn/problem-sets/9 ... /994805396953219072

解：
迪杰斯特拉

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

using namespace std;

const int maxn = 1050;

int n, m, k, ds;
int d[maxn];
bool vis[maxn];
int G[maxn][maxn];

int trans(char *s)
{
    int id;

    if (*s == 'G')
    {
        sscanf(s + 1, "%d", &id);
        id += n;
    }
    else
        sscanf(s, "%d", &id);

    return id; 
}

void DJS(int st)
{
    fill(d, d + maxn, INT_MAX);
    memset(vis, false, sizeof(vis));

    d[st] = 0;

    for (int i = 1; i < n + m; i++)
    {
        int u  = -1, min = INT_MAX;

        for (int j = 1; j <= n + m; j++)
            if (!vis[j] && d[j] < min) min = d[u = j];

        if (u == -1) return;

        vis[u] = true;

        for (int v = 1; v <= n + m; v++)
        {
            if (vis[v] || G[u][v] == INT_MAX) continue;
            if (G[u][v] + d[u] < d[v]) d[v] = G[u][v] + d[u];
        }
    }
}

int main(void) 
{
    // freopen("input.txt", "r", stdin);
    scanf("%d %d %d %d", &n, &m, &k, &ds);
        
    fill(G[0], G[0] + maxn * maxn, INT_MAX);
    
    while (k--)
    {
        char s1[5], s2[5];
        int a, b, l;

        scanf("%s %s %d", s1, s2, &l);
        a = trans(s1);
        b = trans(s2);

        G[a][b] = G[b][a] = l;
    }

    int max_id = -1, max = INT_MIN;
    double ave[maxn];

    for (int i = n + 1; i <= n + m; i++)
    {
        DJS(i);

        int temp = d[1], total = 0;
        bool flag = false;
        for (int j = 1; j <= n; j++)
        {
            if (d[j] > ds)
            {
                flag = true;
                break;
            }

            total += d[j];
            if (d[j] < temp) temp = d[j];
        }

        if (flag) continue;

        ave[i] = (double)total / (double)n;    

        if (temp > max || (temp == max && ave[i] < ave[max_id]))
        {
            max = temp;
            max_id = i;
        }
    }

    if (max_id == -1) puts("No Solution");
    else printf("G%d\n%.1f %.1f\n", max_id - n, (double)max, ave[max_id]);
    
    return 0;
}