pbds.cpp

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto & a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

#include <bits/extc++.h>
using namespace __gnu_pbds;

int main() {
	cin.sync_with_stdio(0); cin.tie(0);
	cin.exceptions(cin.failbit);

	while (true) {
		int n, m, q, s;
		cin >> n >> m >> q >> s;
		if (n == 0) break;

		vector<vector<pii>> adj(n);
		rep(i, 0, m) {
			int u, v, w;
			cin >> u >> v >> w;
			adj[u].push_back({v, w});
		}

		vector<int> distances(n, INT_MAX);
		distances[s] = 0;

		__gnu_pbds::priority_queue<pii, greater<pii>, pairing_heap_tag> Q;
		vector<decltype(Q)::point_iterator> iterators(n);
		rep(i, 0, n) {
			iterators[i] = Q.push({distances[i], i});
		}

		while (!Q.empty()) {
			int u, d;
			tie(d, u) = Q.top();
			if (d == INT_MAX) break;
			Q.pop();

			trav(e, adj[u]) {
				int v, w;
				tie(v, w) = e;
				if (d + w < distances[v]) {
					Q.modify(iterators[v], {d + w, v});
					distances[v] = d + w;
				}
			}
		}
		rep(i, 0, q) {
			int u;
			cin >> u;
			int d = distances[u];
			cout << (d == INT_MAX? "Impossible": to_string(d)) << endl;
		}
		cout << endl;
	}
}

pq.cpp

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto & a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int main() {
	cin.sync_with_stdio(0); cin.tie(0);
	cin.exceptions(cin.failbit);

	while (true) {
		int n, m, q, s;
		cin >> n >> m >> q >> s;
		if (n == 0) break;

		vector<vector<pii>> adj(n);
		rep(i, 0, m) {
			int u, v, w;
			cin >> u >> v >> w;
			adj[u].push_back({v, w});
		}

		vector<int> distances(n, INT_MAX);

		priority_queue<pii> Q;
		Q.push({0, s});

		while (!Q.empty()) {
			int u, d;
			tie(d, u) = Q.top();
			d *= -1;
			Q.pop();
			if (distances[u] != INT_MAX) continue;
			distances[u] = d;

			trav(e, adj[u]) {
				int v, w;
				tie(v, w) = e;
				Q.push({-(d + w), v});
			}
		}
		rep(i, 0, q) {
			int u;
			cin >> u;
			int d = distances[u];
			cout << (d == INT_MAX? "Impossible": to_string(d)) << endl;
		}
		cout << endl;
	}
}

set.cpp

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto & a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int main() {
	cin.sync_with_stdio(0); cin.tie(0);
	cin.exceptions(cin.failbit);

	while (true) {
		int n, m, q, s;
		cin >> n >> m >> q >> s;
		if (n == 0) break;

		vector<vector<pii>> adj(n);
		rep(i, 0, m) {
			int u, v, w;
			cin >> u >> v >> w;
			adj[u].push_back({v, w});
		}

		vector<int> distances(n, INT_MAX);
		distances[s] = 0;

		set<pii> Q;
		rep(i, 0, n) {
			Q.insert({distances[i], i});
		}
		while (!Q.empty()) {
			int u, d;
			tie(d, u) = *Q.begin();
			if (d == INT_MAX) break;
			Q.erase(Q.begin());

			trav(e, adj[u]) {
				int v, w;
				tie(v, w) = e;
				if (d + w < distances[v]) {
					auto it = Q.find({distances[v], v});
					Q.erase(it);
					Q.insert({d + w, v});
					distances[v] = d + w;
				}
			}
		}
		rep(i, 0, q) {
			int u;
			cin >> u;
			int d = distances[u];
			cout << (d == INT_MAX? "Impossible": to_string(d)) << endl;
		}
		cout << endl;
	}
}