// Converted to C++11 by Doubao. #include <iostream> #include <queue> #include <tuple> // C++11中使用std::tuple必须包含此头文件 #include <utility> #include <vector> using namespace std; using i64 = long long; // C++11支持using类型别名 constexpr i64 INF = 0x3f3f3f3f3f3f3f3f; // C++11支持constexpr int main() { ios::sync_with_stdio(false); cin.tie(nullptr); // nullptr是C++11特性 cout.tie(nullptr); int k, m, s; cin >> k >> m >> s; vector<int> a(k + 1); for (int i = 1; i <= k; ++i) cin >> a[i]; int n = 1 << k; vector<vector<pair<int, int>>> graph(n); for (int i = 0; i < m; ++i) { int u, v, c; cin >> u >> v >> c; graph[u].emplace_back(v, c); // C++11支持emplace_back graph[v].emplace_back(u, c); } priority_queue<pair<i64, int>> node1; vector<i64> dist(n, INF); // C++11需显式指定模板参数（CTAD是C++17特性） vector<vector<vector<bool>>> vis(n, vector<vector<bool>>(k + 1, vector<bool>(k + 1, false))); // C++11支持多层vector初始化，需显式模板参数（此处原本已兼容） dist[s] = 0; node1.emplace(0, s); while (!node1.empty()) { // 替换C++17结构化绑定：pair的结构化绑定 pair<i64, int> top_node = node1.top(); node1.pop(); i64 dis = -top_node.first; int cur = top_node.second; if (dis != dist[cur]) continue; // 替换C++17结构化绑定：遍历pair的结构化绑定 for (const auto& edge : graph[cur]) { int nxt = edge.first; int cost = edge.second; if (dist[nxt] > dist[cur] + cost) { dist[nxt] = dist[cur] + cost; node1.emplace(-dist[nxt], nxt); } } vector<tuple<int, int, int>> node2; node2.emplace_back(cur, 0, 0); // C++11支持tuple的emplace_back while (!node2.empty()) { // 替换C++17结构化绑定：tuple的结构化绑定 tuple<int, int, int> back_node = node2.back(); node2.pop_back(); int u = get<0>(back_node); // C++11使用std::get访问tuple元素 int i = get<1>(back_node); int j = get<2>(back_node); if (vis[u][i][j]) continue; vis[u][i][j] = true; if (i == k && dist[u] > dis + a[j]) { dist[u] = dis + a[j]; node1.emplace(-dist[u], u); } else if (i < k) { node2.emplace_back(u, i + 1, j); node2.emplace_back(u ^ (1 << i), i + 1, j + 1); } } } for (int i = 0; i < n; ++i) cout << dist[i] << ' '; return 0; }