1072 Gas Station (30分)

对每个可能的加油站点都进行一次Dijkstra，根据题意找出最符合要求的站点。

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_map>
#include<string>
using namespace std;
const int inf = 0x7fffffff;
int numHouse, numCandidate, numRoad, range;
int map[1024][1024];
int minDistance[1024];
bool visited[1024];
int getIndex(string pos) {
	if (pos[0] == 'G') {
		string temp = pos.substr(1, pos.size() - 1);
		int offset = stoi(temp);
		return offset + numHouse;
	}
	else return stoi(pos);
}
int main() {
	cin >> numHouse >> numCandidate >> numRoad >> range;
	fill(map[0], map[0] + 1024 * 1024, inf);
	for (int i = 0; i < numRoad; i++) {
		string s1, s2;
		int dis, p1, p2;
		cin >> s1 >> s2 >> dis;
		p1 = getIndex(s1);
		p2 = getIndex(s2);
		map[p1][p2] = dis;
		map[p2][p1] = dis;
	}
	int bestLocation = -1, shortest = 0, totalDis = inf;
	for (int k = 1; k <= numCandidate; k++) {
		fill(minDistance, minDistance + 1024, inf);
		fill(visited, visited + 1024, false);
		minDistance[k + numHouse] = 0;
		for (int i = 1; i <= numHouse + numCandidate; i++) {
			int u = -1, minDis = inf;
			for (int j = 1; j <= numHouse + numCandidate; j++) {
				if (!visited[j] && minDis > minDistance[j]) {
					minDis = minDistance[j];
					u = j;
				}
			}
			if (u == -1) {
				break;
			}
			visited[u] = true;
			for (int v = 1; v <= numHouse + numCandidate; v++) {
				if (!visited[v] && map[u][v] != inf) {
					if (map[u][v] + minDis < minDistance[v]) {
						minDistance[v] = map[u][v] + minDis;
					}
				}
			}
		}
		int total = 0, min = inf, farthest = 0;
		for (int i = 1; i <= numHouse; i++) {
			if (minDistance[i] < min) {
				min = minDistance[i];
			}
			if (farthest < minDistance[i]) {
				farthest = minDistance[i];
			}
			total += minDistance[i];
		}
		if (farthest <= range && (min > shortest || 
			min == shortest && total < totalDis || 
			min == shortest && total == totalDis && bestLocation > k)) {
			shortest = min;
			totalDis = total;
			bestLocation = k;
		}
	}
	if (shortest == 0) {
		printf("No Solution");
	} else printf("%s\n%.1f %.1f\n", ("G" + to_string(bestLocation)).c_str(), (double)shortest, (double)totalDis / numHouse);
}