1 #include <cstdio> 2 #include <vector> 3 #include <algorithm> 4 #include <cstring> 5 #include <functional> 6 #include <queue> 7 using namespace std; 8  9 #define Node pair<int, int>10 const int maxk = 20 + 2;11 const int INF = 1000000000;12 const int maxm = 200000 + 5;13 const int maxn = 20000 + 5;14 15 struct Edge {16     int to, w, nxt;17     Edge(int to = 0, int w = 0, int nxt = 0) : to(to), w(w), nxt(nxt) {};18 };19 20 int n, m, k, full_set;21 int tot, head[maxn], dis[maxk][maxk], f[1048576][maxk], depend[maxk], bin[maxk];22 int d[maxn];23 bool vis[maxn];24 Edge e[maxm << 1];25 26 int read() {27     int x = 0, f = 1; char ch = getchar();28     while (ch < ‘0‘ || ch > ‘9‘) { if (ch == ‘-‘) f = -1; ch = getchar(); };29     while (ch >= ‘0‘ && ch <= ‘9‘) { x = x * 10 + ch - ‘0‘; ch = getchar(); }30     return x * f;31 }32 33 void add_edge(int u, int v, int w) {34     e[++tot    ].to = v, e[tot].w = w, e[tot].nxt = head[u], head[u] = tot;35 }36 37 // 求第(1 ~ k + 1)号节点到其余节点的单源最短路38 void dijkstra(int x) {39     priority_queue<Node, vector<Node>, greater<Node> > pq;40     for (int i = 1; i <= n; i++) d[i] = INF;41     for (int i = 1; i <= n; i++) vis[i] = 0;42     d[x] = 0;43     pq.push(make_pair(0, x));44     while (!pq.empty()) {45         int cur = pq.top().second; pq.pop();46         if (vis[cur]) continue; else vis[cur] = 1;47         for (int i = head[cur]; i; i = e[i].nxt) {48             if (d[cur] + e[i].w < d[e[i].to]) {49                 d[e[i].to] = d[cur] + e[i].w;50                 pq.push(make_pair(d[e[i].to], e[i].to));51             }52         }53     }54     for (int i = 1; i <= k + 1; i++) dis[x][i] = d[i];55     dis[x][k + 2] = d[n];56 }57 58 void dp() {59     for (int old_set = 0; old_set <= full_set; old_set++) // 枚举节点集合60         for (int cur = 1; cur <= k + 1; cur++) { // 枚举cur为源点61             if (f[old_set][cur] == -1) continue; // 不存在此状态的表示的路径则返回62             for (int nxt = 2; nxt <= k + 1; nxt++) {  //枚举nxt为汇点63                 int new_set = (old_set | bin[nxt - 2]); // 将nxt号节点纳入路径集合64                 if ((old_set & depend[nxt]) == depend[nxt]) // 判断在nxt号节点停留前是否已经在题目要求的节点停留过65                     if (f[old_set][cur] + dis[cur][nxt] < f[new_set][nxt] || f[new_set][nxt] == -1) // 更新最短路66                         f[new_set][nxt] = f[old_set][cur] + dis[cur][nxt];67             }68         }69 }70 71 int main() {72     bin[0] = 1; for (int i = 1; i < 22; i++) bin[i] = bin[i - 1] << 1; // bin[i]表示(i - 2)号节点是否纳入路径73     n = read(); m = read(); k = read(); full_set = bin[k] - 1; // full_set表示2 ~ (k + 1)号节点的全集74     for (int i = 1, u, v, w; i <= m; i++) { // 建图75         u = read(); v = read(); w = read();76         add_edge(u, v, w);77         add_edge(v, u, w);78     }79     for (int i = 1; i <= k + 1; i++) dijkstra(i); // 求出1 ~ (k + 1)号节点到其余节点的单源最短路80     int x = read();81     for (int i = 1, u, v; i <= x; i++) {82         u = read(); v = read();83         depend[v] += bin[u - 2]; // 表示u号(用二进制的第u - 2位表示)节点在v号节点前停留84     }85     memset(f, -1, sizeof(f)); f[0][1] = 0; // 初始化,f[i][j]表示经过i集合（范围2 ~ k + 1）中所有节点*且当前停留在j号节点*的最短路86     dp(); // 求出走完前(1 ~ k + 1) 号节点最终停留在第i号节点的最短路87     int ans = INF;88     for (int i = 1; i <= k + 1; i++)89         if (f[full_set][i] != -1) ans = min(ans, f[full_set][i] + dis[i][k + 2]); // 找出走完(1 ~ k + 1)号节点停留在i到n的最短路90     printf("%d", ans); // 输出91     return 0;92 }