https://ac.nowcoder.com/acm/problem/16122

旅行商问题(板子题):每个城市都得经过且仅经过一次

通过数据范围和题目模型容易看出是旅行商问题，故直接状压dp(刚开始还傻不拉几的用并查集写QAQ)
思路(旅行商问题的常见状态设置):
状态表示:dp[st][i]:走过的城市的状态为st，最后一个到达得城市为第i个城市
状态转移:dp[i][j] = min(dp[k][q] + dist[j][q])(其中dist[j][q]是dist[j][q]的最短路)
该问题满足最优子结构的证明：参见Most powerful的证明，原理一样
AC代码

#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false); cin.tie(0)
#define ll long long
#define ull unsigned long long
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rep(i, l, r) for (int i = l; i <= r; ++i)
#define per(i, l, r) for (int i = l; i >= r; --i)
#define mset(s, _) memset(s, _, sizeof(s))
#define mcpy(s, _) memcpy(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define vi vector<int>
#define vpii vector<pii> 
#define mp(a, b) make_pair(a, b)
#define pll pair <ll, ll>
#define fir first
#define sec second
#define inf 0x3f3f3f3f
inline int lowbit(int x) {return x & -x;} 
template< typename T > inline void get_min(T &x, T y) {if(y < x) x = y;}
template< typename T > inline void get_max(T &x, T y) {if(x < y) x = y;}
inline int read() {
  int x = 0, f = 0; char ch = getchar();
  while (!isdigit(ch)) f |= ch == '-', ch = getchar();
  while (isdigit(ch)) x = 10 * x + ch - '0', ch = getchar();
  return f ? -x : x;
}
template<typename T> inline void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
template<typename T> inline void print(T x, char let) {
  print(x), putchar(let);
}

const int N = 200 + 10, M = 5e3  + 10, mod = 100000000;
int n, m, r;
int dist[N][N];
vi tar;

void floyd() {
    for(int k = 1; k <= n; k ++ ) {
        for(int i = 1; i <= n; i ++ ) {
            for(int j = 1; j <= n; j ++ ) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
}

ll dp[1 << 15][15];

int main() {
    cin >> n >> m >> r; 
    mset(dist, 0x3f);
    rep(i, 1, r) {
        int t; cin >> t; tar.pb(t - 1);
    }
    rep(i, 1, m) {
        int a, b, c; cin >> a >> b >> c;
        dist[a - 1][b - 1] = dist[b - 1][a - 1] = min(dist[a - 1][b - 1], c);
    }

    floyd();

    mset(dp, 0x3f);
    for(int i = 0; i < (1 << r); i ++ ) {
        int cnt = 0, id;
        for(int j = 0; j < r; j ++ ) {
            if(i >> j & 1) {
                cnt ++ ; id = j;
            }
        }
        if(cnt == 1) dp[i][id] = 0;
    }

    for(int i = 0; i < (1 << r); i ++ ) {
        for(int j = 0; j < r; j ++ ) {
            int x = tar[j];
            if(i >> j & 1) {
                for(int k = 0; k < r; k ++ ) {
                    if(k != j && (i >> k) & 1) {
                        int y = tar[k];
                        dp[i][j] = min(dp[i][j], dp[i - (1 << j)][k] + dist[x][y]);
                    }
                 }
            }
        }
    }

    ll ans = inf;
    for(int i = 0; i < r; i ++ ) {
        ans = min(ans, dp[(1 << r) - 1][i]);
    }

    cout << ans << endl;

    return 0;
}