欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-03-13 12:57:53
...

题目

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);
}