最短路

输入第一行包含三个整数N,M,C，表示企鹅国城市的个数、快捷通道的个数以及题面中提到的给定的常数C。
接下来的M行，每行三个正整数F_i,T_i,V_i(1≤F_i≤N,1≤T_i≤N,1≤V_i≤100)，分别表示对应通道的起点城市标号、终点城市标号和通过这条通道需要消耗的时间。
最后一行两个正整数A,B(1≤C≤100)，表示企鹅豆豆选择的起点城市标号和终点城市标号。

C++(clang++ 11.0.1) 解法, 执行用时: 312ms, 内存消耗: 51468K, 提交时间: 2023-03-19 18:01:47

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

int main(){
  ios::sync_with_stdio(false);
  int N, M, C; cin >> N >> M >> C;
  vector<vector<pair<int, int>>> G(1<<17);
  while (M--) {
    int F, T, V; cin >> F >> T >> V;
    G[F].push_back({T, V});
  }
  for (int i = 1; i < 1<<17; i++) {
    for (int j = 1; j < 1<<17; j<<=1) {
      G[i].push_back({i^j,  j*C});
    }
  }
  int A, B; cin >> A >> B;
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Q;
  vector<int> D(1<<17, 0x3f3f3f3f);
  D[A] = 0;
  Q.push({0, A});
  while (!Q.empty()) {
    auto [d, s] = Q.top(); Q.pop();
    if (D[s] != d) continue;
    if (s == B) break;
    for (auto &[t, v]: G[s]) {
      int tmp = D[s] + v;
      if (tmp >= D[t]) continue;
      D[t] = tmp;
      Q.push({D[t], t});
    }
  }
  cout << D[B] << endl;
}

详情