UVa 11813 - Shopping

#include <stdio.h>
#include <vector>
#include <queue>
#include <utility>
#include <string.h>
#include <algorithm>
using namespace std;

#define MAX_NODES 100000
#define MAX_EDGES 100000
#define MAX_NODES_TO_VISIT 10

const int INF = 2147483647;
typedef pair<int, int> PII;
class Dijkstra {
private:
	int N;
	vector<vector<PII> > edges;
	vector<int> dist, dad;
public:
	Dijkstra(int number_of_nodes) {
		N = number_of_nodes;
		edges = vector<vector<PII> >(N);
	}
	void addEdge(int from, int to, int weight) {
		edges[from].push_back(make_pair(weight, to));
	}
	void run(int start_node) {
		// use priority queue in which top element has the "smallest" priority
		priority_queue<PII, vector<PII>, greater<PII> > Q;
		dist = vector<int>(N, INF);
		dad = vector<int>(N, -1);
		Q.push(make_pair(0, start_node));
		dist[start_node] = 0;
		while (!Q.empty()) {
			PII p = Q.top();
			//if (p.second == end_node)
			//break;
			Q.pop();
			int here = p.second;
			for (vector<PII>::iterator it = edges[here].begin(); it != edges[here].end(); it++) {
				if (dist[here] + it->first < dist[it->second]) {
					dist[it->second] = dist[here] + it->first;
					dad[it->second] = here;
					Q.push(make_pair(dist[it->second], it->second));
				}
			}

		};
	}
	int getDistanceTo(int end_node) {
		return dist[end_node];
	}
	vector<int> getPathTo(int end_node) {
		vector<int> path;
		for (int i = end_node; i != -1; i = dad[i])
			path.push_back(i);
		reverse(path.begin(), path.end());
		return path;
	}
};

int node_to_visit[MAX_NODES_TO_VISIT];

int main() {
	int cases;
	for (scanf("%d", &cases); cases; cases--) {
		int number_of_nodes, number_of_edges;
		scanf("%d%d", &number_of_nodes, &number_of_edges);
		Dijkstra dijkstra = Dijkstra(number_of_nodes);
		for (int i = 0; i < number_of_edges; i++) {
			int from, to, weight;
			scanf("%d%d%d", &from, &to, &weight);
			dijkstra.addEdge(from, to, weight);
			dijkstra.addEdge(to, from, weight);
		}
		int number_of_nodes_to_visit;
		scanf("%d", &number_of_nodes_to_visit);
		for (int i = 0; i < number_of_nodes_to_visit; i++)
			scanf("%d", &node_to_visit[i]);

		int distance[MAX_NODES_TO_VISIT][MAX_NODES_TO_VISIT];
		distance[0][0] = 0;
		for (int i = 1; i < number_of_nodes_to_visit; i++) {
			dijkstra.run(node_to_visit[i]);
			for (int j = 0; j < i; j++) {
				distance[i][j] = dijkstra.getDistanceTo(node_to_visit[j]);
				distance[j][i] = dijkstra.getDistanceTo(node_to_visit[j]);
			}
			distance[i][i] = 0;
		}

		int T[1 << MAX_NODES_TO_VISIT][MAX_NODES_TO_VISIT];
		memset(T, 127, sizeof(T));

		int final_mask = (1 << number_of_nodes_to_visit) - 1;
		dijkstra.run(0);
		typedef pair<int, pair<int, int> > PIII;
		priority_queue<PIII, vector<PIII>, greater<PIII> > q;
		for (int i = 0; i < number_of_nodes_to_visit; i++) {
			T[1 << i][i] = dijkstra.getDistanceTo(node_to_visit[i]);
			q.push(make_pair(T[1 << i][i], make_pair(1 << i, i)));
		}

		int sol = INF, finals_count = number_of_nodes_to_visit;
		while (!q.empty()) {
			PIII now = q.top();
			PII state = now.second;
			if (state.first == final_mask) {
				if (now.first + T[1 << state.second][state.second] < sol)
					sol = now.first + T[1 << state.second][state.second];
				if (--finals_count == 0)
					break;
			}
			q.pop();
			for (int i = 0; i < number_of_nodes_to_visit; i++) {
				int new_mask = state.first | (1 << i);
				int new_cost = T[state.first][state.second] + distance[state.second][i];
				if (new_mask != state.first && new_cost < T[new_mask][i]) {
					T[new_mask][i] = new_cost;
					q.push(make_pair(new_cost, make_pair(new_mask, i)));
				}
			}
		}
		printf("%d\n", sol);

	}

	return 0;
}