Rezultati

Up. imeNalogaJezikRezultatČas oddaje
ASMx64-2018 Avtocesta C++ Se ne prevede 04. okt '18 @ 19:27

Izpis prevajalnika:
source.c++: In function ‘void Dijkstra(int)’:
source.c++:18:65: error: wrong number of template arguments (0, should be 1)
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<> > pq;
                                                                 ^
In file included from /usr/include/c++/5/string:48:0,
                 from /usr/include/c++/5/bits/locale_classes.h:40,
                 from /usr/include/c++/5/bits/ios_base.h:41,
                 from /usr/include/c++/5/ios:42,
                 from /usr/include/c++/5/ostream:38,
                 from /usr/include/c++/5/iostream:39,
                 from source.c++:1:
/usr/include/c++/5/bits/stl_function.h:372:12: note: provided for ‘template<class _Tp> struct std::greater’
     struct greater : public binary_function<_Tp, _Tp, bool>
            ^
source.c++:18:67: error: template argument 3 is invalid
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<> > pq;
                                                                   ^
source.c++:20:5: error: request for member ‘push’ in ‘pq’, which is of non-class type ‘int’
  pq.push(make_pair(0, source));
     ^
source.c++:22:13: error: request for member ‘empty’ in ‘pq’, which is of non-class type ‘int’
  while (!pq.empty()) {
             ^
source.c++:23:17: error: request for member ‘top’ in ‘pq’, which is of non-class type ‘int’
   auto min = pq.top();
                 ^
source.c++:24:6: error: request for member ‘pop’ in ‘pq’, which is of non-class type ‘int’
   pq.pop();
      ^
source.c++:35:8: error: request for member ‘push’ in ‘pq’, which is of non-class type ‘int’
     pq.push(make_pair(distances[v].first, v));
        ^

Ocenjevani program (avtocesta.cpp):
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
#include <climits>
using namespace std;
int zemljevid[52][52]; // 0 - zgrajeno, -1 - ne obstaja
bool povezana[52];
int steviloMest;
vector<pair<int, int>> pomembna;

pair<int, vector<int>> distances[52];

void Dijkstra(int source) {
	distances[source] = make_pair(0, vector<int>());
	distances[source].second.emplace_back(source);
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<> > pq;

	pq.push(make_pair(0, source));
	int u, v, weight;
	while (!pq.empty()) {
		auto min = pq.top();
		pq.pop();
		u = min.second;

		for (int j = 1; j <= steviloMest; j++) {
			if (zemljevid[u][j] == -1) continue;
			v = j;
			weight = zemljevid[u][j];

			if (distances[v].first > distances[u].first + weight/* || (distances[v].first == distances[u].first + weight && distances[u].second.size() + 1 > distances[v].second.size())*/) {
				distances[v] = make_pair(distances[u].first + weight, vector<int>(distances[u].second));
				distances[v].second.emplace_back(v);
				pq.push(make_pair(distances[v].first, v));
			}
		}
	}
}

int spremeniGraf() {
	pair<pair<int, int>, vector<int>> naredi;
	int min = INT_MAX;
	
	for (unsigned int j = 0; j < pomembna.size(); j++) {
		if (povezana[pomembna[j].first]) continue;
		fill_n(distances, 52, make_pair(INT_MAX, vector<int>()));
		Dijkstra(pomembna[j].first);
		//for (int k = 1; k <= steviloMest; k++) cout << distances[k].first << endl;
		//system("pause");

		if (distances[pomembna[j].second].first < min) {
			min = distances[pomembna[j].second].first;
			naredi = make_pair(make_pair(pomembna[j].first, pomembna[j].second), distances[pomembna[j].second].second);
		}
		else if (distances[pomembna[j].second].first == min && distances[pomembna[j].second].second.size() > naredi.second.size()) {
			min = distances[pomembna[j].second].first;
			naredi = make_pair(make_pair(pomembna[j].first, pomembna[j].second), distances[pomembna[j].second].second);
		}

		/*for (int i = 1; i <= steviloMest; i++) {
			if (i == pomembna[j] || find(pomembna.begin(), pomembna.end(), i) == pomembna.end()) {
				continue;
			}

			if (distances[i].first < min) {
				min = distances[i].first;
				naredi = make_pair(make_pair(pomembna[j], i), distances[i].second);
			}
			else if (distances[i].first == min && distances[i].second.size() > naredi.second.size()) {
				min = distances[i].first;
				naredi = make_pair(make_pair(pomembna[j], i), distances[i].second);
			}
		}*/
		//cout << "-----" << min << endl;
		//cout << naredi.first.first << " " << naredi.first.second << endl;
	}

	//cout << "-----" << min << endl;
	//cout << naredi.first.first << " " << naredi.first.second << endl;
	povezana[naredi.first.first] = true;
	povezana[naredi.first.second] = true;

	//for (int k = 0; k < naredi.second.size(); k++) cout << naredi.second[k] << endl;


	for (unsigned int j = 0; j < naredi.second.size() - 1; j++) {
		zemljevid[naredi.second[j]][naredi.second[j + 1]] = 0;
		zemljevid[naredi.second[j+1]][naredi.second[j]] = 0;
	}

	return min;
}

int main() {
	int steviloCest, steviloPomembnih, rez = 0, x, y, d;
	cin >> steviloMest >> steviloCest;
	memset(povezana, 0, sizeof(povezana));

	for (int i = 1; i <= steviloMest; i++) {
		for (int j = 1; j <= steviloMest; j++) {
			zemljevid[i][j] = -1;
		}
	}

	for (int i = 0; i < steviloCest; i++) {
		cin >> x >> y >> d;
		zemljevid[x][y] = d;
		zemljevid[y][x] = d;
	}

	cin >> steviloPomembnih;

	for (int i = 0; i < steviloPomembnih; i++) {
		cin >> x >> y;

		pomembna.emplace_back(make_pair(x, y));
	}

	//bool vsa;

	for (int i = 0; i < steviloPomembnih; i++) {
		rez += spremeniGraf();
	}

	/*while (true) {
		vsa = true;
		for (unsigned int j = 0; j < pomembna.size(); j++) {
			if (!povezana[j]) {
				vsa = false;
				break;
			}
		}
		if (vsa) break;

		
	}*/

	cout << rez << endl;

	return 0;
}