1072 Gas Station (30 分)

出错先检查初始化、题意理解

有事儿没事儿记得初始化！！！

记得初始化！！！

初始化！！！

尤其是全局变量多次当新的用，用之前初始化！！

怎么肥四初始化一次就没在用了又当新的用之前初始化了？？？

什么INF、0、-1、false

为一句total = 0自闭大半天值得吗？？？

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

#define INF 0x3fffffff
using namespace std;
int NHouse, NGas, mm, max_range, max_min = -1, best = -1;
int total, best_total;
int graph[1050][1050];

int str2int(char str[]) {
    int temp = 0, size = strlen(str), first = 0, wei = 1;
    if (str[0] == 'G') first = 1;
    for (int i = size - 1; i >= first; --i) {
        temp += (wei * (str[i] - '0'));
        wei *= 10;
    }
    if (first) temp += 1000;
    return temp;
}

int Dijkstra(int src) {
    int dist[1050];
    bool visited[1050] = {false};
    fill(visited, visited + 1050, false);
    fill(dist, dist + 1050, INF);
    dist[src] = 0;
    for (int i = 0; i < NHouse + NGas; ++i) {
        int mDist = INF, index = -1;
        for (int j = 1; j <= 1000 + NGas; ++j) {
            if (!visited[j] && dist[j] < mDist) {
                mDist = dist[j], index = j;
            }
            if (j == NHouse) j = 1000;
        }
        if (index != -1) {
            visited[index] = true;
            for (int j = 1; j <= 1000 + NGas; ++j) {
                if (!visited[j] && graph[index][j] != INF) {
                    int newd = dist[index] + graph[index][j];
                    if (newd < dist[j]) dist[j] = newd;
                }
                if (j == NHouse) j = 1000;
            }
        } else return -1;
    }
    int min_dist = INF;
    total = 0;
    for (int k = 1; k <= NHouse; ++k) {
        if (dist[k] > max_range) return -1;
        if (dist[k] < min_dist) {
            min_dist = dist[k];
        }
        total += dist[k];
    }
    return min_dist;
}

int main() {
    fill(graph[0], graph[0] + 1050 * 1050, INF);
    scanf("%d%d%d%d", &NHouse, &NGas, &mm, &max_range);
    char s1[6], s2[6];
    int v1, v2, weight;
    for (int i = 0; i < mm; ++i) {
        scanf("%s%s%d", s1, s2, &weight);
        v1 = str2int(s1), v2 = str2int(s2);
        graph[v1][v2] = graph[v2][v1] = min(graph[v2][v1], weight);
    }
    for (int i = 0; i < 1050; ++i) graph[i][i] = 0;
    for (int i = 1001; i <= 1000 + NGas; ++i) {
        int temp_min = Dijkstra(i);
        if (temp_min == -1 || temp_min == INF) continue;
        if (temp_min > max_min) {
            max_min = temp_min;
            best = i;
            best_total = total;
        } else if (temp_min == max_min) {
            if (total < best_total) {
                best = i;
                best_total = total;
            } // the gas station with a lower number is preferable
        }
    }
    if (best != -1) {
        printf("G%d\n%d.0 %.1lf\n", best - 1000, max_min, best_total * 1.0 / (NHouse * 1.0));
    } else printf("No Solution\n");
    return 0;
}