laekov

比较简单易懂的状压。

最初想懒一下把起点和终点也压进来然后发现刚好会超一点空间。然后不压进来的话就是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);

}