之前本沙茶成功地在網(wǎng)絡(luò)流圖中搞出Dancing Link邊表，那么對于一般的圖，是否也能用Dancing Link邊表呢？答案是肯定的。
邊類型（帶權(quán)的，不帶邊權(quán)的圖把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++;
}
在一般的圖中應(yīng)用Dancing Link邊表的優(yōu)勢：【1】能夠有效處理刪邊刪點(diǎn)問題；【2】在無向圖中，能夠很快找到一條邊對應(yīng)的逆向邊；【3】最大的優(yōu)勢是：如果要從某一條單點(diǎn)鏈表（其實(shí)整個邊表可以看成N個單點(diǎn)鏈表的并，N為圖中的點(diǎn)數(shù)）的中間開始遍歷，或者逆向遍歷整個表的話，一般的鄰接鏈表幾乎不可能完成，一般的邊表也很麻煩，這種Dancing Link邊表則可以很快搞定。不過它也有缺點(diǎn)：空間消耗比鄰接鏈表和一般邊表大一些（不過這個影響不大）。
【應(yīng)用實(shí)例】
PKU1062（PKU上少有的中文題）
很水的最短路問題。將每個物品當(dāng)成一個點(diǎn)，若j可作為i的優(yōu)惠品則連邊<i, j>，邊權(quán)為優(yōu)惠價格，然后，枚舉等級限制（由于物品1是必須選的，因此設(shè)最大等級限制為lmt，物品1的等級為V，則可在[V-lmt, V]范圍內(nèi)枚舉最低等級，最高等級就是(最低等級+lmt)），將所有不在等級限制內(nèi)的點(diǎn)全部刪除（其實(shí)不用真刪除，只要設(shè)一個del數(shù)組避開它們即可），求從結(jié)點(diǎn)1到各結(jié)點(diǎn)的最短路，則min(dist[i]+cs[i])（dist[i]表示1到i的最短路，cs[i]表示直接購買物品i的價格）就是結(jié)果。
代碼（2Y，一開始把solve里的g[j]弄成g[i]了囧……靜態(tà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;
}