Description

Abu runs a delivery service where he deliver items from one city to another. As with any business, Abu wants to decrease his cost as much as possible. The further he travel, the more fuel he will use.
In any particular day, Abu have k items to deliver. Each item needs to be delivered from a start city to a destination city. Each city is represented by an integer. Because of his business policies, he can only deliver one item at a time. However, he can deliver the items in any order that he wants, as long as he deliver all of them. So, everyday he starts at an item's start city and deliver the item to its destination city. Then, he goes to the next items's start city and deliver the item to the its destination city. And, he does this until he does not have any item left to deliver.
From experimentation, Abu notices that the distance he travels change if he change the order of his delivery. He thought, he can save a lot of money if he knows the best delivery order. He knows that you are very good at solving this kind of problem. So he wants you to solve it for him. Given a list of cities, a list of roads between the cities (and the road's length), and a description of deliveries he must do, determine what is the minimum total travel distance, given that he execute his delivery in the most efficient order.
Every road is bidirectional and there can be more than one road between two cities. Abu can use any road as many time as he wants.

Solution

题意：给出一个图，k组路线，需要找到走完这个k组路线的最小花费。
图片说明
思路：dp+最短路
如上图，每两个点代表一次delivery过程，可以看出，黑色的线代表的花费是无法避免的，因此，真正决定答案的优劣取决于红色的线。其中，红色的线(当前路线的终点到下一条路线的起点)的大小取决于我们的选取方案，由于k的范围(k <= 18)较小，可以通过状压dp枚举所有方案，最后通过dp的思想更新最优的答案。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e4 + 5;
int n, m, k;
bool vis[N];
struct qnode {
  int v; ll cost;
  bool operator < (const qnode &s) const {
    return cost > s.cost;
  }
  qnode(int _v = 0, ll _cost = 0): v(_v), cost(_cost){}
};
vector<pair<int, ll> > G[N];
ll dist[N];
ll p[20][20], dp[1 << 18][20];
void Dijkstra(int start) { // 最短路
  for(int i = 1; i <= n; i++) {
    dist[i] = 1e18;
    vis[i] = false;
  }
  priority_queue<qnode> q;
  q.push(qnode(start, 0));
  dist[start] = 0;
  while(!q.empty()) {
    qnode tmp = q.top(); q.pop();
    int u = tmp.v;
    if(vis[u]) continue;
    vis[u] = true;
    for(int i = 0; i < G[u].size(); i++) {
      int v = G[u][i].first;
      ll w = G[u][i].second;
      if(!vis[v] && dist[v] > dist[u] + w) {
        dist[v] = dist[u] + w;
        q.push(qnode(v, dist[v]));
      }
    }
  }
}
pair<int, int> query[20]; // k组路线
int main() {
  cin >> n >> m >> k;
  for(int i = 1; i <= m; i++) {
    int u, v; ll w; cin >> u >> v >> w;
    G[u].push_back({v, w});
    G[v].push_back({u, w});
  }
  for(int i = 1; i <= k; i++) {
    cin >> query[i].first >> query[i].second;
  }
  for(int i = 0; i < 20; i++) {
    for(int j = 0; j < 20; j++) {
      p[i][j] = 1e18;   // i的起点到j的终点的距离
    }
  }
  for(int i = 1; i <= k; i++) {
    Dijkstra(query[i].first); // 起点
    for(int j = 1; j <= k; j++) {
      //cout << query[i].first << ' ' << query[j].second << ' ' << dist[query[j].second] << "\n";
      p[i][j] = dist[query[j].second]; 
    }
  }
  for(int i = 0; i < (1 << k); i++) {
    for(int j = 0; j <= k; j++) {
      dp[i][j] = 1e18; // i 状态时处于 j 点的花费
    }
  }
  for(int i = 0; i < k; i++) {
    dp[1 << i][i] = p[i + 1][i + 1];
  }
  ll ans = 1e18;
  for(int i = 0; i < (1 << k); i++) {
    for(int j = 0; j < k; j++) { // 枚举起点
      if(!(i & (1 << j))) continue; // 该状态不走该起点
      //cout << (i & (1 << j)) << "\n";
      for(int l = 0; l < k; l++) { // 枚举终点
        if(i & (1 << l)) continue; // 该终点走过
        dp[i | (1 << l)][l] = min(dp[i | (1 << l)][l], dp[i][j] + p[j + 1][l + 1] + p[l + 1][l + 1]);
        if((i | (1 << l)) + 1 == (1 << k)) { // 全部都走完了
          //cout << "state:" << (i | (1 << i)) << "\n";
          ans = min(ans, dp[i | (1 << l)][l]);
          //cout << ans << "\n";
        }
      }
    }
  } 
  if(ans == 1e18) {
    cout << -1 << '\n';
  } else {
    cout << ans << '\n';
  }
  return 0; 
}