笔记汇总
最短路
Johnson 全源最短路
我们建立一个虚拟源点，向其它点连一条$0$边，然后跑 $spfa$，
再在原图上根据这个最短路值做差分，这样就可以用 $dijkstra$ 计算。
#include <bits/stdc++.h>
using namespace std;
const int N = 3e3 + 10, M = 9e3 + 10, INF = 0x3f3f3f3f;
typedef pair<int, int> PII;
int n, m;
int h[N], e[M], w[M], ne[M], idx;
int dist[N], hig[N], q[N], cnt[N];
bool st[N];
void add(int a, int b, int c) // 添加一条边a->b，边权为c
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
bool spfa(int S) // 如果存在负环，则返回true，否则返回false。
{
memset(hig, 0x3f, sizeof hig);
int hh = 0, tt = 0;
hig[S] = 0;
q[tt ++ ] = S, st[S] = true;
while (hh != tt)
{
int t = q[hh ++ ];
if (hh == N) hh = 0;
st[t] = false;
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (hig[j] > hig[t] + w[i])
{
hig[j] = hig[t] + w[i];
cnt[j] = cnt[t] + 1;
if (cnt[j] > n) return true; // 算上 0, 一共有 n + 1 个点
if (!st[j])
{
st[j] = true;
q[tt ++ ] = j;
if (tt == N) tt = 0;
}
}
}
}
return false;
}
void dijkstra(int S) // 求1号点到n号点的最短路距离
{
memset(st, false, sizeof st);
memset(dist, 0x3f, sizeof dist);
dist[S] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, S});
while (heap.size())
{
auto t = heap.top();
heap.pop();
int ver = t.second, distance = t.first;
if (st[ver]) continue;
st[ver] = true;
for (int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[ver] + w[i])
{
dist[j] = dist[ver] + w[i];
heap.push({dist[j], j});
}
}
}
}
int main()
{
memset(h, -1, sizeof h);
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i ++ )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
for (int i = 1; i <= n; i ++ ) add(0, i, 0);
if (spfa(0)) return puts("-1") & 0;
for (int u = 1; u <= n; u ++ )
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
w[i] = w[i] + hig[u] - hig[j];
}
for (int i = 1; i <= n; i ++ )
{
dijkstra(i);
long long ans = 0;
for (int j = 1; j <= n; j ++ )
ans += j * (dist[j] == INF ? 1e9 : dist[j] - hig[i] + hig[j]);
printf("%lld\n", ans);
}
return 0;
}
二染色法
// 1. 二进制分组，答案的一对点必有一位二进制不同，所以一定会被枚举到。
// 注意跑两边，有向图可能不连通。
// 2. 正反染色法，对于一个两点间的最短路径，我们可以枚举它们之间的点，
// 对于dijkstra算法，如果一个点迭代到了另一个点，那一点就是它们间的最短路径
// 如果我们以每个关键点为起点同样以每个关键点为终点，就可以求出最短路径，
// 但是我们必须要是两个点，所以处理完到其它点的最短路径，和其它点到它们的最短路径后，
// 通过插入点和插入边的方式就可以求出了。
// 如，关键点A, B : 1. A -> B -> C 可以 A -> B <- C 2. A -> B 可以 A -> B
#include <bits/stdc++.h>
#define LL long long
using namespace std;
inline LL read(){
LL x = 0,f = 1; char c = getchar();
while (c != EOF && !isdigit(c)) {if (c == '-') f = -1;c = getchar();}
while (isdigit(c)) {x = x * 10 + c - '0';c = getchar();}
return x * f;
}
inline void write(LL x){
if (x < 0) putchar('-'),x = -x;
if (x > 9) write(x/10); putchar(x%10+'0');
}
inline void writeln(LL x){ write(x),putchar('\n'); }
const int N = 100005,M = 500005;
int Fr[M<<2],To[M<<2],Ne[M<<2],Dis[M<<2],He1[N],He2[N],_k;
inline void add(int *He,int x,int y,int z){
++_k,Fr[_k] = x,To[_k] = y,Dis[_k] = z,Ne[_k] = He[x],He[x] = _k;
}
int T,n,m,k,p[N];
const LL INF = 1ll<<60;
int f1[N],f2[N];
LL dis1[N],dis2[N];
struct Node{
int x; LL d;
Node (int xx = 0,LL dd = 0){ x = xx,d = dd; }
inline bool operator < (Node x) const{ return d > x.d; }
}t;
priority_queue<Node>Heap;
void Dij_1(){ //dis1 : p[i] -> x
int i;
while (!Heap.empty()) Heap.pop();
for (i = 1; i <= n; ++i) dis1[i] = INF,f1[i] = -1;
for (i = 1; i <= k; ++i) dis1[p[i]] = 0,f1[p[i]] = p[i],Heap.push(Node(p[i],0));
int p,x;
while (!Heap.empty()){
t = Heap.top(); Heap.pop();
if (t.d == dis1[t.x])
for (p = He1[t.x]; p ; p = Ne[p]) if (dis1[To[p]] > dis1[t.x] + Dis[p]){
dis1[To[p]] = dis1[t.x] + Dis[p];
f1[To[p]] = f1[t.x];
Heap.push(Node(To[p],dis1[To[p]]));
}
}
}
void Dij_2(){ //dis2 : x -> p[i]
int i;
for (i = 1; i <= n; ++i) dis2[i] = INF,f2[i] = -1;
for (i = 1; i <= k; ++i) dis2[p[i]] = 0,f2[p[i]] = p[i],Heap.push(Node(p[i],0));
int p,x;
while (!Heap.empty()){
t = Heap.top(); Heap.pop();
if (t.d == dis2[t.x])
for (p = He2[t.x]; p ; p = Ne[p]) if (dis2[To[p]] > dis2[t.x] + Dis[p]){
dis2[To[p]] = dis2[t.x] + Dis[p];
f2[To[p]] = f2[t.x];
Heap.push(Node(To[p],dis2[To[p]]));
}
}
}
LL ans;
int main(){
int i,u,v,w;
T = read();
while (T--){
_k = 0;
memset(He1,0,sizeof(He1));
memset(He2,0,sizeof(He2));
n = read(),m = read(),k = read();
while (m--){ u = read(),v = read(),w = read(); if (u^v) add(He1,u,v,w),add(He2,v,u,w); }
for (i = 1; i <= k; ++i) p[i] = read();
Dij_1();
Dij_2();
ans = INF;
for (i = 1; i <= n; ++i) if (f1[i] ^ f2[i]) ans = min(ans,dis1[i] + dis2[i]);
for (i = 1; i <= _k; i += 2) if (f1[Fr[i]]^f2[To[i]])
ans = min(ans,dis1[Fr[i]] + dis2[To[i]] + Dis[i]);
writeln(ans);
}
return 0;
}
二分最短路
二分信息来拆点。
分层图最短路
// https://www.cnblogs.com/aitejiu/p/16448925.html
/*
我们可能遇到这样的图论模型：在一个正常的图上可以进行 k 次决策，
对于每次决策，不影响图的结构，只影响目前的状态或代价。
同时这个图论模型和经典的最短路有关，这样我们可以考虑运用分层图最短路。
*/
// 我们只需要建立可以产生贡献的边就行。
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;
typedef long long ll;
const int INF = 1e17 + 11;
const int maxn = 3e5 + 333;
const int N = 1e5 + 11;
ll dis[maxn];
int vis[maxn];
struct Node {
int p;
ll len;
int nxt;
}G[maxn * 2];
int z;
int head[maxn];
void add(int be, int en, ll len) {
G[++z].p = en;
G[z].nxt = head[be];
G[z].len = len;
head[be] = z;
}
bool operator <(const Node a, const Node b) {
return a.len > b.len;
}
void dij(int be) {
for (int i = 0; i < maxn; i++) {
vis[i] = 0;
dis[i] = 1e17;
}
dis[be] = 0;
priority_queue<Node>que;
Node ccc;
ccc.len = 0;
ccc.p = be;
que.push(ccc);
while (que.size()) {
Node cn = que.top();
que.pop();
if (vis[cn.p]) continue;
vis[cn.p] = 1;
for (int i = head[cn.p]; i; i = G[i].nxt) {
int p = G[i].p;
if (dis[p] > dis[cn.p] + G[i].len) {
dis[p] = dis[cn.p] + G[i].len;
Node ccc;
ccc.len = dis[p];
ccc.p = p;
que.push(ccc);
}
}
}
return ;
}
struct cn {
int x, y, id;
}que[maxn];
bool cp1(cn a, cn b) {
if (a.x == b.x) return a.y < b.y;
return a.x < b.x;
}
bool cp2(cn a, cn b) {
if (a.y == b.y) return a.x < b.x;
return a.y < b.y;
}
int n, m;
int main() {
scanf("%d%d", &n, &m);
int s = m;
int t = m+1;
int x,y;
for (int i = 0; i < m; i++) {
scanf("%d%d", &que[i].x, &que[i].y);
que[i].id = i;
}
scanf("%d%d", &que[s].x, &que[s].y);
scanf("%d%d", &que[t].x, &que[t].y);
que[s].id = s;
que[t].id = t;
int len = m + 2;
sort(que, que + len, cp1);
for (int i = 1; i < len; i++) {
if (que[i - 1].x == que[i].x) {
ll ln = que[i].y - que[i - 1].y;
int be = que[i - 1].id;
int en = que[i].id;
add(be, en, 2 * ln);
add(en, be, 2 * ln);
}
}
sort(que, que + len, cp2);
for (int i = 1; i < len; i++) {
if (que[i - 1].y == que[i].y) {
ll ln = que[i].x - que[i-1].x;
int be = que[i - 1].id;
int en = que[i].id;
add(be+N, en+N, 2*ln);
add(en+N, be+N, 2*ln);
}
}
for (int i = 0; i < m; i++) { // 转向
add(i, i + N, 1);
add(i + N, i, 1);
}
add(s, s + N, 0); // 起点和终点是不确定方向的
add(s + N, s, 0);
add(t, t + N, 0);
add(t + N, t, 0);
dij(s);
if (dis[t] >= 1e13 ) {
printf("-1\n");
}
else {
printf("%lld\n", min(dis[t], dis[t + N]));
}
return 0;
}
图论拆点
// 拆点的经典题目
// 在不考虑剩余系的情况下，等价于dfs找环，
// 我们可以用拆点多加一维信息，从而解决。
/*
1、当前状态没有被搜到过：这种情况直接继续搜索，并继承它的后继状态的答案即可。
2、当前状态被搜到过了：说明此时构成了一个环，
那么所有环上的点就都是可以被经过无限次的，类似于找环的方法，
把环上的点弄出来去重，加入答案即可。
*/
#include <bits/stdc++.h>
using namespace std;
const int mod = 2520;
int n;
int insta[1010][2530], ans[1010][2530];
int w[1010];
int dep[1010][2530];
int son[1010][12], len[1010];
int sta[2530000];
int cnt[1010];
inline int dfs(int x, int y) { // 找环
insta[x][y] = 1;
if(ans[x][y]) return ans[x][y];
sta[dep[x][y]] = x;
int newx = son[x][y % len[x]], newy = (y + w[newx]) % mod;
// 找到要向哪个点转移
if(insta[newx][newy]) {
if(ans[newx][newy]) return ans[x][y] = ans[newx][newy];
int l = dep[newx][newy], r = dep[x][y];
for(int i = l; i <= r; i++) cnt[sta[i]] = 0;
for(int i = l; i <= r; i++) if(cnt[sta[i]] == 0) cnt[sta[i]] = 1, ans[x][y]++;
return ans[x][y];
}
dep[newx][newy] = dep[x][y] + 1;
ans[x][y] = dfs(newx, newy);
return ans[x][y];
}
int main() {
ios :: sync_with_stdio(false);
cin >> n;
for(int i = 1; i <= n; i++) cin >> w[i], w[i] = (w[i] % mod + mod) % mod;
for(int i = 1; i <= n; i++) {
cin >> len[i];
for(int j = 0; j < len[i]; j++) cin >> son[i][j];
}
int q;
cin >> q;
while(q--) {
int x, c;
cin >> x >> c;
c = (c % mod + mod) % mod;
cout << dfs(x, (c + w[x]) % mod) << endl;
}
return 0;
}
对偶图交通规划
#include<fstream>
#include<algorithm>
#include<queue>
const int A=360000,B=1210000,C=2200,D=55,INF=1000000000;
using namespace std;
int n,m,T,tl,to[A][2],hd[A],dis[A],w[D][D],gt[D],f[D][D];
int is[C],id[C],cf[C];
struct edge
{
int to,nt,ct;
}e[B];
struct question
{
int x3,p,t;
}q[D];
#define noi pair<int,int>
priority_queue<noi,vector<noi>,greater<noi> >ccf;
void add(int u,int v,int w)
{
e[tl].to=v,e[tl].ct=w,e[tl].nt=hd[u];
hd[u]=tl++;
}
bool cmp(const question &a,const question &b)
{
return a.p<b.p;
}
void path(int s,int U)
{
for(int i=0;i<U;++i)dis[i]=INF;
ccf.push(make_pair(dis[s]=0,s));
while(!ccf.empty())
{
int u=ccf.top().second;
ccf.pop();
for(int z=hd[u];z!=-1;z=e[z].nt)
{
int v=e[z].to;
if(dis[u]+e[z].ct<dis[v])
ccf.push(make_pair(dis[v]=dis[u]+e[z].ct,v));
}
while(!ccf.empty()&&dis[ccf.top().second]<ccf.top().first)
ccf.pop();
}
}
int main()
{
scanf("%d%d%d",&n,&m,&T);
for(int i=0,ti=0;i+1<n;++i)
for(int j=0;j<m;++j,++ti)
scanf("%d",&to[ti][0]);
for(int i=0,ti=0;i<n;++i,++ti)
for(int j=0;j+1<m;++j,++ti)
scanf("%d",&to[ti][1]);
for(int i=0;i+1<m;++i)
id[i]=to[i][1],cf[i]=i;
for(int i=0;i+1<n;++i)
id[m+i]=to[i*m+m-1][0],cf[m+i]=i*(m-1)+m-2;
for(int i=0;i+1<m;++i)
id[m+n+i]=to[(n-1)*m+m-2-i][1],cf[m+n+i]=(n-2)*(m-1)+m-2-i;
for(int i=0;i+1<n;++i)
id[m+m+n+i]=to[(n-2-i)*m][0],cf[m+m+n+i]=(n-2-i)*(m-1);
id[m-1]=id[m+n-1]=id[m+m+n-1]=id[m+m+n+n-1]=-1;
while(T--)
{
int k;
scanf("%d",&k);
tl=0;
for(int i=(m-1)*(n-1)+k-1;i>=0;--i)hd[i]=-1;
for(int i=0,ti=1,tj=0;i+1<n;++i,ti+=2,++tj)
for(int j=1;j+1<m;++j,++ti,++tj)
add(tj,tj+1,to[ti][0]),
add(tj+1,tj,to[ti][0]);
for(int i=1,ti=m,tj=0;i+1<n;++i,++ti)
for(int j=0;j+1<m;++j,++ti,++tj)
add(tj,tj+m-1,to[ti][1]),
add(tj+m-1,tj,to[ti][1]);
for(int i=0;i<k;++i)
{
scanf("%d%d%d",&q[i].x3,&q[i].p,&q[i].t);
--q[i].p;
}
sort(q,q+k,cmp);
q[k]=q[0];
int u=(m-1)*(n-1),gi=0;
add(u,u+k-1,q[0].x3),
add(u+k-1,u,q[0].x3);
for(int i=0;i<k;++i,++u)
{
if(i)add(u,u-1,q[i].x3);
if(i+1<k)add(u,u+1,q[i+1].x3);
for(int j=q[i].p;j!=q[i+1].p;j=(j+1==m+m+n+n?0:j+1))
if(id[j]>=0)
add(u,cf[j],id[j]),
add(cf[j],u,id[j]);
if(q[i].t!=q[i+1].t)gt[gi++]=u;
}
for(int i=0;i<gi;++i)
{
path(gt[i],u);
for(int j=0;j<gi;++j)
w[i][j]=dis[gt[j]],f[i][j]=INF;
if(i+1<gi)f[i][i+1]=w[i][i+1];
}
for(int i=3;i<gi;i+=2)
for(int l=0;l+i<gi;++l)
{
f[l][l+i]=min(f[l][l+i],f[l+1][l+i-1]+w[l][l+i]);
for(int k=1;k<i;k+=2)
f[l][l+i]=min(f[l][l+i],f[l][l+k]+f[l+k+1][l+i]);
}
printf("%d\n",f[0][gi-1]);
}
return 0;
}
可删最短路及最长路
[HNOI2014]道路堵塞
最短路删边模板题，容易想到用数据结构去维护。
对于答案路径，一定是在原最短路上走一段路，然后从最短路上一点绕开断路，走到最短路上另一点，再继续走最短路，回到终点。
所以可以用堆去维护所有的合法答案，将每一步计算分为插入和删除两部分，删除可以用懒惰删除法，插入则需要用$spfa$搜索合法答案。
为了减小$spfa$的搜索量，我们可以预处理出最短路径上的点和距离，
/*
存图+对最短路上的点顺序编号+求到终点的最短路值（后面会用到）
顺序枚举最短路上的点
对于当前的点，SPFA寻找后继节点
由于这里找到最短路上的点后需要快速得到到终点的长度，并插入堆
所以预处理一个到终点的最短路值，同时减少没有必要的尝试，减少时间
从堆顶取出元素，如果路径没有绕过断边，踢出堆
如果堆顶无元素，输出-1，否则输出解
更新到当前点的最短路（之前走的都是绕远路来的）
如果这一条边的终点是n，结束
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int head[200010], dis[200010], n, m, l, tot;
int vis[200010];
int stu[200010], rk[200010], s[200010], from[200010];
int g[200010];
struct edge {
int next, from, to, wt;
} a[1000010];
struct node {
int to, val;
bool operator < (const node &fff) const {
return val > fff.val;
}//重载 < 运算符
};
priority_queue <node> st;
inline void add (int u, int v, int w) {
a[++ tot] = (edge) {head[u], u, v, w};
head[u] = tot;
}//简单的链式前向星
inline void spfa (int sa) {
queue <int> q;
q.push (sa);
vis[sa] = 1;
while (! q.empty ()) {
int k = q.front ();
q.pop ();
vis[k] = 0;
for (int i = head[k]; i; i = a[i].next) {
if (stu[i]) // 当其无法通行时
continue;
int to = a[i].to;
/*
对于当前的点，SPFA寻找后继节点。
*/
if (dis[to] > dis[k] + a[i].wt) {
dis[to] = dis[k] + a[i].wt;
if (from[to])
st.push ((node) {from[to], dis[to] + g[from[to]]});//扔进优先队列
else if (! vis[to])
q.push (vis[to] = to);
}
}
}
}
int main (void) {
ios::sync_with_stdio (0);
cin.tie (0);
cout.tie (0);
cin >> n >> m >> l;
for (int i = 1, u, v, w; i <= m; ++ i) {
cin >> u >> v >> w;//加边
add (u, v, w);
}
for (int i = 1; i <= l; ++ i) {
cin >> rk[i];//最短路径上的路
stu[rk[i]] = 1;//它有可能会堵车
s[i + 1] = a[rk[i]].to; // 边的终点
from[s[i + 1]] = i + 1;
}
for (int i = l; i >= 1; -- i) {
g[i] = g[i + 1] + a[rk[i]].wt;//原最短路上第i个点到第n个点的最短路
}
memset (dis, 127 / 3, sizeof (dis));
dis[1] = 0;
from[1] = s[1] = 1;//最短路径上的第一个点
spfa (1);
for (int i = 1; i <= l; ++ i) {
while (! st.empty () and st.top ().to <= i)
st.pop ();
if (st.empty ())
cout << -1 << endl;//由上的分析
else
cout << st.top ().val << endl;
dis[a[rk[i]].to] = dis[s[i]] + a[rk[i]].wt; // 计算加上这条边后的长度
spfa (s[i + 1]); // 一个个加上
}
return 0;
}
拓扑图上的删点最长路
重点是怎么从删第$i$个点递推至删第$i+1$个点，
其实我们可以用可删堆，先插入所有的距离，再去动态处理合法和不合法的距离。
/*
拓扑图上，删边求最长路径长度，
先以所有点为起点所有点为终点做一次二染色，
因为本题无环，所以我们可以已经可以求出最长路。
那么操作就很简单了，只需要枚举每一个节点并删除，弹出和这个节点有关的路径，
记录这时的最大值。然后再把这个节点放回去就可以。
*/
#include<bits/stdc++.h>
#include<queue>
#define ri register int
using namespace std;
struct Edge{
int next;
int to;
int dist;
}e[2000200];
struct de_heap{ // 可删堆
priority_queue<int> a,b;
void push(int x){a.push(x);} // 插入堆
void pop(int x){b.push(x);} // 删除堆
int top()
{
while(!b.empty() && a.top()==b.top()) // 在插入不能在删除
a.pop(),b.pop();
return a.top();
}
}p;
int n,m,ans,key;
int head[500050],cnt;
void add_edge(int from,int to,int dist)
{
e[++cnt].to=to;
e[cnt].next=head[from];
e[cnt].dist=dist;
head[from]=cnt;
}
int in[500050],tp[500050],sum; //拓扑排序求最长路
queue<int> q;
void tpsort()
{
for(ri i=1;i<=n;i++)
if(!in[i]) q.push(i);
while(!q.empty())
{
int u=q.front();
tp[++sum]=u;
q.pop();
for(ri i=head[u]; i; i=e[i].next)
if(e[i].dist==1)
{
in[e[i].to]--;
if(in[e[i].to]==0) q.push(e[i].to);
}
}
}
//这里这么bfs的缘故是因为拓扑排序求最长路，一定是从拓扑序低的地方向高的地方转移，所以每次只需要扩展一次。
int dis1[500050],dis2[500050];
void bfs1(int now)
{
for(ri i=head[now]; i; i=e[i].next)
if(e[i].dist==1) dis1[e[i].to]=max(dis1[e[i].to],dis1[now]+1);
}
void bfs2(int now)
{
for(ri i=head[now]; i; i=e[i].next)
if(e[i].dist==-1) dis2[e[i].to]=max(dis2[e[i].to],dis2[now]+1);
}
int main()
{
scanf("%d%d",&n,&m);
for(ri i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add_edge(u,v,1); //1代表正图，-1代表反图
add_edge(v,u,-1);
in[v]++;
}
tpsort();
for(ri i=1;i<=sum;i++)
bfs1(tp[i]);
for(ri i=sum;i>=1;i--)
bfs2(tp[i]);
for(ri i=1;i<=n;i++) p.push(dis2[i]);
ans=p.top();
for(ri i=1;i<=n;i++)
{
int u=tp[i]; //删除节点
p.pop(dis2[u]);
for(ri j=head[u]; j; j=e[j].next)
if(e[j].dist==-1) p.pop(dis2[u]+dis1[e[j].to]+1);
int tmp=p.top();
if(tmp<ans) ans=tmp,key=u;
for(ri j=head[u]; j; j=e[j].next)
if(e[j].dist==1) p.push(dis1[u]+dis2[e[j].to]+1);
p.push(dis1[u]);
}
printf("%d %d",key,ans);
}
无向图上边权可修改最短路
/*
边权可修改的最短路问题。先分情况讨论：
t 不在最短路径上，边权变大：答案不变
t 不在最短路径上，边权变小：处理反图，与答案作比较
t 在最短路径上，且边权变小：答案变小，可以O(1)计算
t 在最短路径上，且边权变大：等价于删边最短路，可以用线段树维护。
就是求min(最短路的长度-原边长+新边长，不经过修改的这条边的最短路长度)
*/
问题可等价于删边最短路，这里用线段树实现，
线段树上的每段区间 $l,r$ 的值表示 整个图不经过 $E$（最短路径）上 $l$ 到 $r$ 编号的边的最短路长度，
需要支持区间取 $min$，单点查询，因为查询都在修改之后，所以还可以用 $multiset$ 维护，在左端点插入，右端点删除，查询最小值即可。注意去掉左端点大于右端点的情况。
状压最短路
本题有后效性，不能只用状压$DP$，所以用状压 $+$ $SPFA$，结点是 $bug$ 修复的状态，
注意这样的图不用将边建出来。
#include<bits/stdc++.h>
using namespace std;
int pop=0,n,m,s,t;
int v[4000000],d[4000000];
queue<int>q;
int b1[1000],b2[1000],f1[1000],f2[1000],xx[1000];
void spfa(){
//初始化
memset(v,0,sizeof(v));
memset(d,0x7f,sizeof(d));
d[s]=0;while(q.size())q.pop();
q.push(s);
while(q.size()){
int x=q.front(),y;q.pop();
v[x]=0;
for(int i=1;i<=m;i++){
//枚举补丁
if((b1[i]&x)==b1[i]&&(b2[i]&x)==0){
//判断当前节点是否可以做为起点
y=((x|f1[i])^f1[i])|f2[i];
//求出终点
if(d[x]+xx[i]<d[y]){
//spfa的松弛操作
d[y]=d[x]+xx[i];
if(!v[y]){
v[y]=1;
q.push(y);
}
}
}
}
}
printf("%d\n",d[t]==0x7f7f7f7f?0:d[t]);
}
int main()
{
scanf("%d%d",&n,&m);
t=0;s=(1<<n)-1;
char a[1000],b[1000];
for(int i=1;i<=m;i++){
//预处理出每个补丁对应的b1,b2,f1,f2
scanf("%d%s%s",&xx[i],a,b);
b1[i]=b2[i]=f1[i]=f2[i]=0;
for(int j=0;j<n;j++){
if(a[j]=='+')
b1[i]|=(1<<j);
if(a[j]=='-')
b2[i]|=(1<<j);
if(b[j]=='+')
f2[i]|=(1<<j);
if(b[j]=='-')
f1[i]|=(1<<j);
}
}
spfa();
return 0;
}
