Gas Station 4 FBR

PAT1072.cpp

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

#define MAXINT 2147483647

int dis[1200][1200];
int n, m, k, d;
char a[5], b[5];
int tmp;
int ansidx;
int ans;
int anstot;
int defaultFill;

int getId(char* id)
{
    if(id[0] == 'G')
    {
        return atoi(id + 1) + n - 1;
    }
    else return atoi(id) - 1;
}

void dijkstra(int op)
{
    bool vis[1200];
    int dist[1200];
    memset(vis, 0, sizeof(vis));
    for(int i = 0; i < n + m; i++)
    {
        dist[i] = dis[op][i];
    }
    vis[op] = true;

    for(int i = 0; i < n + m; i++)
    {
        int cur = -1;
        int mindis = MAXINT;
        for(int j = 0; j < n + m; j++)
        {
            if((!vis[j] && (cur == -1 || mindis > dist[j])) && dist[j] != defaultFill)
            {
                cur = j;
                mindis = dist[j];
            }
        }
        if(cur == -1) break;

        vis[cur] = true;
        for(int j = 0; j < n + m; j++)
        {
            if(!vis[j] && dis[cur][j] != defaultFill)
            {
                if(dist[cur] + dis[cur][j] < dist[j])
                {
                    dist[j] = dist[cur] + dis[cur][j];
                }
            }
        }
    }

    int mindis = MAXINT;
    int tot = 0;
    for(int i = 0; i < n; i++)
    {
        if(dist[i] > d) return;

        tot += dist[i];
        if(dist[i] < mindis)
        {
            mindis = dist[i];
        }
    }

    if(ans < mindis)
    {
        ans = mindis;
        ansidx = op;
        anstot = tot;
    }
    else
    if(ans == mindis && anstot > tot)
    {
        anstot = tot;
        ansidx = op;
    }
}

int main()
{
    while(~scanf("%d%d%d%d", &n, &m, &k, &d))
    {
        memset(dis, 0x7f, sizeof(dis));
        defaultFill = dis[0][0];
        for(int i = 0; i < k; i++)
        {
            scanf("%s%s%d", a, b, &tmp);
            int aa = getId(a);
            int bb = getId(b);
            dis[aa][bb] = tmp;
            dis[bb][aa] = tmp;
        }

        ansidx = -1;
        ans = -1;
        anstot = 0;

        for(int i = n; i < n + m; i++) dijkstra(i);

        if(ansidx == -1)
        {
            printf("No Solution\n");
        }
        else
        {
            printf("G%d\n%.1lf %.1lf\n", ansidx - n + 1, (double)ans, (double)(anstot) / (double)(n));
        }
    }

    return 0;
}