比较简单易懂的状压。
最初想懒一下把起点和终点也压进来然后发现刚好会超一点空间。然后不压进来的话就是100MB左右，很好奇MAIN上面64MB的内存应该怎么做。拿MAP么？
代码各种难看啊郁闷。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct edge {
int t, v;
edge *next;
};
#define pow2(x) (1<<(x))
typedef pair <int, int> dspr;
const int maxn = 20009;
const int maxe = 400009;
const int maxk = 20;
const int maxz = pow2(20) + 3;
int n, m, k, d[maxn];
int f[maxz][maxk], ds[maxk], dt[maxk], dk[maxk][maxk], ans;
int g, pr[maxk];
edge *ep, *head[maxn];
dspr hp[maxe];
inline void addEdge(int u, int v, int w) {
ep-> t = v;
ep-> v = w;
ep-> next = head[u];
head[u] = ep ++;
}
void dijkstra(int p0) {
int th = 1;
hp[0] = dspr(0, p0);
memset(d, -1, sizeof(d));
while (th) {
dspr g = hp[0];
pop_heap(hp, hp + (th --));
if (d[g. second] > -1)
continue;
d[g. second] = - g. first;
for (edge* e = head[g. second]; e; e = e-> next)
if (d[e-> t] == -1) {
hp[th] = dspr(g. first - e-> v, e-> t);
push_heap(hp, hp + (++ th));
}
}
}
int main() {
#ifndef ONLINE_JUDGE
//freopen("in.txt", "r", stdin);
#endif
scanf("%d%d%d", &n, &m, &k);
memset(head, 0, sizeof(head));
ep = new edge[m * 2];
for (int i = 0; i < m; ++ i) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
addEdge(u, v, w);
addEdge(v, u, w);
}
for (int i = 2; i <= k + 1; ++ i) {
dijkstra(i);
for (int j = 2; j <= k + 1; ++ j)
dk[i - 2][j - 2] = d[j];
ds[i - 2] = d[1];
dt[i - 2] = d[n];
}
memset(pr, 0, sizeof(pr));
scanf("%d", &g);
for (int i = 0; i < g; ++ i) {
int u, v;
scanf("%d%d", &u, &v);
pr[v - 2] |= pow2(u - 2);
}
if (k) {
memset(f, -1, sizeof(f));
for (int i = 0; i < k; ++ i)
if (!pr[i])
f[pow2(i)][i] = ds[i];
for (int i = 0, ei = pow2(k); i < ei; ++ i)
for (int j = 0; j < k; ++ j)
if (f[i][j] > -1)
for (int t = 0; t < k; ++ t)
if (!(pow2(t) & i) && ((i & pr[t]) == pr[t])) {
int zn = pow2(t) | i;
if (f[zn][t] == -1 || f[zn][t] > f[i][j] + dk[j][t])
f[zn][t] = f[i][j] + dk[j][t];
}
ans = -1;
for (int i = 0, et = pow2(k) - 1; i < k; ++ i)
if (f[et][i] > -1)
if (ans == -1 || f[et][i] + dt[i] < ans)
ans = f[et][i] + dt[i];
}
else {
dijkstra(1);
ans = d[n];
}
printf("%d\n", ans);
}