题意：对于区间[l, r]有两种操作，第一种是缩减区间，将其变为[l+1,r]或者[l,r+1]，第二种是扩张区间，将其变为[l-1,r]或者[l,r+1]，其中有两种阻断操作(l,r,dir,c)，第一种dir='L’可以使[l,r]不变成[l+1,r]，第二种dir='R’可以使[l,r]不变成[l,r-1]，花费均为c。起点是[1,n]，要使操作过程中始终无法到达[i,i]的形式，问最小花费是多少。 解法：首先这是一个网格图，起点是右上角，终点是对角线上的点，要使起点无法到达终点，着一些阻断操作，相当于砍断了一些边，那么对于样例该如何建边，看图。
3 4 1 3 L 10 1 3 R 3 1 2 L 1 1 2 R 1
实际上就是建立超级源和超级汇，然后每一条边的意义在于砍断这条边，在这上面s到t跑最短路就可。运用到的思想是最小割的思想，狼抓兔子和这题很像，但是出题人貌似卡掉了求最小割的做法，我ISAP一直段错误 。
代码：
#include<bits/stdc++.h> #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define _for(n,m,i) for (register int i = (n); i < (m); ++i) #define _rep(n,m,i) for (register int i = (n); i <= (m); ++i) #define lson rt<<1, l, mid #define rson rt<<1|1, mid+1, r #define PI acos(-1) #define eps 1e-8 #define rint register int using namespace std; typedef long long LL; typedef pair<LL, int> pli; typedef pair<int, int> pii; typedef pair<double, int> pdi; typedef pair<LL, LL> pll; typedef pair<double, double> pdd; typedef map<int, int> mii; typedef map<char, int> mci; typedef map<string, int> msi; template<class T> void read(T &res) { int f = 1; res = 0; char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { res = res * 10 + c - '0'; c = getchar(); } res *= f; } const int ne[8][2] = {1, 0, -1, 0, 0, 1, 0, -1, -1, -1, -1, 1, 1, -1, 1, 1}; const LL INF = 1e15; const int N = 3e5+10; const LL Mod = 1234567891; const int M = 2e6+10; struct xx { int next, to; LL w; xx() {} xx(int next, int to, LL w) { this->next = next; this->to = to; this->w = w; } }e[M]; int tot, head[N]; void Add(int u, int v, LL w) { e[++tot] = xx(head[u], v, w); head[u] = tot; e[++tot] = xx(head[v], u, w); head[v] = tot; } int s, t, u, v; priority_queue<pli, vector<pli>, greater<pli> > q; LL dis[N], vis[N]; void dij() { for(int i = 0; i <= t; ++i) dis[i] = INF, vis[i] = 0; dis[s] = 0; q.push(make_pair(dis[s], s)); while(!q.empty()) { u = q.top().second; q.pop(); if(vis[u]) continue; vis[u] = 1; for(int i = head[u]; i; i = e[i].next) { v = e[i].to; if(dis[v] > dis[u] + e[i].w) { dis[v] = dis[u] + e[i].w; q.push(make_pair(dis[v], v)); } } } } int n, m; int main() { scanf("%d%d", &n, &m); int x, y; char dir; LL c; int u, v; s = 0; t = n*n+1; for(int i = 0; i < m; ++i) { scanf("%d %d %c %lld", &x, &y, &dir, &c); u = (x-1)*n + y; if(dir == 'R') v = max(s, u-n); else v = u, u = (y == n ? t : v + 1); Add(u, v, c); } dij(); if(dis[t] >= INF) puts("-1"); else printf("%lld\n", dis[t]); return 0; }