之前本沙茶成功地在网络流图中搞出Dancing Link边表，那么对于一般的图，是否也能用Dancing Link边表呢？答案是肯定的。
边类型（带权的，不带边权的图把len域去掉即可）：
struct edge {
int a, b, len, pre, next;
} ed[MAXM];
初始化表头：
void init_d()
{
re(i, n) ed[i].a = ed[i].pre = ed[i].next = i;
if (n % 2) m = n + 1; else m = n;
}
加边（这里是加有向边，如果加无向边的话，再加一条边<b, a, len>即可）：
void add_edge(int a, int b, int len)
{
ed[m].a = a; ed[m].b = b; ed[m].len = len; ed[m].pre = ed[a].pre; ed[m].next = a; ed[a].pre = m; ed[ed[m].pre].next = m++;
}
在一般的图中应用Dancing Link边表的优势：【1】能够有效处理删边删点问题；【2】在无向图中，能够很快找到一条边对应的逆向边；【3】最大的优势是：如果要从某一条单点链表（其实整个边表可以看成N个单点链表的并，N为图中的点数）的中间开始遍历，或者逆向遍历整个表的话，一般的邻接链表几乎不可能完成，一般的边表也很麻烦，这种Dancing Link边表则可以很快搞定。不过它也有缺点：空间消耗比邻接链表和一般边表大一些（不过这个影响不大）。
【应用实例】
PKU1062（PKU上少有的中文题）
很水的最短路问题。将每个物品当成一个点，若j可作为i的优惠品则连边<i, j>，边权为优惠价格，然后，枚举等级限制（由于物品1是必须选的，因此设最大等级限制为lmt，物品1的等级为V，则可在[V-lmt, V]范围内枚举最低等级，最高等级就是(最低等级+lmt)），将所有不在等级限制内的点全部删除（其实不用真删除，只要设一个del数组避开它们即可），求从结点1到各结点的最短路，则min(dist[i]+cs[i])（dist[i]表示1到i的最短路，cs[i]表示直接购买物品i的价格）就是结果。
代码（2Y，一开始把solve里的g[j]弄成g[i]了囧……静态查错V5啊……神犇不要鄙视）：
#include <iostream>
#include <stdio.h>
#include <queue>
#include <utility>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
typedef pair <int, int> i_i;
typedef priority_queue <i_i, vector<i_i>, greater<i_i> > pqi_i;
const int MAXN = 100, MAXM = 30000, INF = ~0U >> 2;
struct edge {
int a, b, len, pre, next;
} ed[MAXM];
int n, m, s, lmt, cs[MAXN], g[MAXN], dist[MAXN], res = INF;
bool del[MAXN];
pqi_i q;
void init_d()
{
re(i, n) ed[i].a = ed[i].pre = ed[i].next = i;
if (n % 2) m = n + 1; else m = n;
}
void add_edge(int a, int b, int len)
{
ed[m].a = a; ed[m].b = b; ed[m].len = len; ed[m].pre = ed[a].pre; ed[m].next = a; ed[a].pre = m; ed[ed[m].pre].next = m++;
}
void init()
{
int b0, x, y;
scanf("%d%d", &lmt, &n);
init_d();
re(i, n) {
scanf("%d%d%d", &cs[i], &g[i], &x);
re(j, x) {
scanf("%d%d", &b0, &y);
add_edge(i, --b0, y);
}
}
}
void sol1()
{
re(i, n) if (!del[i]) dist[i] = INF + 1; q.push(i_i(0, s));
int i, j, d0, d1;
while (!q.empty()) {
d0 = q.top().first; i = q.top().second; q.pop();
if (dist[i] == INF + 1) {
dist[i] = d0;
for (int p=ed[i].next; p != i; p=ed[p].next) {
j = ed[p].b;
if (!del[j]) {
d1 = d0 + ed[p].len; q.push(i_i(d1, j));
}
}
}
}
re(i, n) if (!del[i]) {
d0 = cs[i] + dist[i];
if (d0 < res) res = d0;
}
}
void solve()
{
int lf, rt; s = 0;
re3(i, 0, lmt) {
lf = g[s] - i; rt = lf + lmt;
re(j, n) del[j] = g[j] < lf || g[j] > rt;
sol1();
}
}
void pri()
{
printf("%d\n", res);
}
int main()
{
init();
solve();
pri();
return 0;
}