PTA甲级考试真题练习72——1072 Gas Station

题目

思路

图的最短路径算法,我这里使用的dijstra算法，注意排序的顺序即可，将加油站放在家的后面
我这里犯了个错误：得到输入字符串对应的索引时，仅仅使用字符串长度判断到底是纯数字还是加油站G开头的字符串，忽略了数字大于等于10的情况，应该判断首字母是不是‘G’来区分

代码

#include <iostream>
#include <string>
#include<algorithm>
#include<vector>
using namespace std;
#define nmax 1100
#define inf 999999

int n1, n2, m, maxpath,n;
int graph[nmax][nmax];
int dst[nmax];
int book[nmax];

typedef struct {
	int min;
	double ave;
	int _index;
}Info;

vector<Info> vec;

int getIndex(string str) {
	stringstream ss;
	int num;
	if (str[0] == 'G') {
		str.erase(str.begin());
		ss << str;
		ss >> num;
		return num + n1 - 1;
	}
	else {
		ss << str;
		ss >> num;
		return num - 1;
	}
}

void Dijskra(int u) {
	memset(book, 0, sizeof(book));
	for (int i = 0; i < n; ++i) {
		dst[i] = graph[u][i];
	}
	book[u] = 1;
	for (int i = 0; i < n - 1; ++i) {
		int min = inf;
		for (int j = 0; j < n; ++j) {
			if (book[j] == 0 && dst[j] < min) {
				min = dst[j];
				u = j;
			}
		}
		book[u] = 1;
		for (int j = 0; j < n; ++j) {
			if (book[j] == 0 && dst[j] > dst[u] + graph[u][j])
				dst[j] = dst[u] + graph[u][j];
		}
	}
}

bool cmp(const Info& a, const Info& b) {
	if (a.min != b.min)
		return a.min > b.min;
	else
		if (a.ave != b.ave)
			return a.ave < b.ave;
		else
			return a._index < b._index;
}
int main()
{
	cin >> n1 >> n2 >> m >> maxpath;
	n = n1 + n2;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			graph[i][j] = inf;
	for (int i = 0; i < m; ++i) {
		string a, b;
		int weight;
		cin >> a >> b >> weight;
		int one = getIndex(a);
		int two = getIndex(b);
		graph[one][two] = graph[two][one] = weight;
	}
	for (int i = n1; i < n; ++i) {
		Dijskra(i);
		Info info;
		int sum = 0;
		bool can = true;
		int _min = inf;
		for (int j = 0; j < n1; ++j) {
			if (dst[j] > maxpath) {
				can = false;
				break;
			}
			_min = min(_min, dst[j]);
			sum += dst[j];
		}
		if (can) {
			info.min = _min;
			info._index = i - n1 + 1;
			info.ave = (double)sum / n1;
			vec.emplace_back(info);
		}
	}
	if (vec.empty()) {
		cout << "No Solution";
		return 0;
	}
	sort(vec.begin(), vec.end(), cmp);
	printf("G%d\n", vec[0]._index);
	printf("%.1f %.1f", (double)vec[0].min, vec[0].ave);
}