题目大意：
给你一个区间 ([l,r]) 这个区间可能做两种操作：
- 收缩， ([l,r]) 变成 ([l,r-1]) 或者 ([l+1,r])
- 扩张，([l,r]) 变成 ([l-1,r]) 或者 ([l,r+1])
但是当 (l==r) 的时候，这个区间就不会有任何的变化了，你不想看到这样的情况，所以你要禁止一些操作。
((l,r,dir,c)) 对于这个元组表示：
- 如果 (dir=L) 那么你可以花费 (c) 禁止 ([l,r]) 到 ([l + 1,r]) 的改变
- 如果 (dir = R) 那么你可以花费 (c) 禁止 ([l,r]) 到 ([l,r-1]) 的改变。
算出最小的花费保证 (l\,!=r) ，如果不可能，则输出 (-1)
题解：
这个题目还是有点难的，知道这个是一个网络流了，但是我还是不知道怎么建图，先看看官方题解吧：
看完之后就先去学了一些怎么把平面图转对偶图然后求最短路。
学习推荐博客：https://www.cnblogs.com/lher/p/7856451.html
看完之后就应该先去自己写一下狼抓兔子这个题目了：https://www.luogu.com.cn/problem/P4001
狼抓兔子题解：https://www.cnblogs.com/EchoZQN/p/13322359.html
自己做完就应该知道怎么把平面图转化成对偶图了。
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
#define debug(x) printf("debug:%s=%d
",#x,x);
//#define debug(x) cout << #x << ": " << x << endl;
using namespace std;
typedef long long ll;
const int maxn = 500+5;
int t,s;
struct node{
ll w;
int u,v;
node(int u=0,int v=0,ll w=0):u(u),v(v),w(w){}
};
struct heapnode{
ll d;
int u;
heapnode(ll d,int u) : d(d),u(u) {}
bool operator<(const heapnode &a) const{
return a.d<d;
}
};
vector<node>e[2*maxn*maxn];
void add(int u,int v,ll w){
// printf("u=%d v=%d w=%lld
",u,v,w);
e[u].push_back(node(u,v,w));
e[v].push_back(node(v,u,w));
}
ll d[2*maxn*maxn];
bool vis[2*maxn*maxn];
priority_queue<heapnode>que;
void dij(int s){
while(!que.empty()) que.pop();
for(int i=0;i<=t+10;i++) d[i]=inf64;
d[s]=0;
que.push(heapnode(0,s));
while(!que.empty()){
heapnode x=que.top();que.pop();
int u=x.u;
if(vis[u]) continue;
vis[u]=1;
for(int i=0;i<e[u].size();i++){
node now=e[u][i];
if(d[now.v]>d[u]+now.w){
d[now.v]=d[u]+now.w;
que.push(heapnode(d[now.v],now.v));
}
}
}
}
ll w[maxn][maxn][2];
char ss[10];
int main(){
int n,m;
scanf("%d%d",&n,&m);
memset(w,inf64,sizeof(w));
s = 0, t = (n-1)*(n-1)+1;
for (int i = 1; i <= m; i ++) {
int u,v,c;
scanf("%d%d%s%d",&u,&v,ss,&c);
if(ss[0]=='L') w[u][v][1]=c;
else w[u][v][0]=c;
}
for(int i=1;i<n-1;i++){
for(int j=i;j<n;j++){
int u = (i-1)*(n-1)+j;
int x = (i-1)*(n-1)+j+1;
int y = i*(n-1)+j;
if(i==j) y ++;
if(x<=i*(n-1)) add(u,x,w[i][j+1][1]);
add(u,y,w[i+1][j+1][0]);
// printf("i=%d j=%d
",i,j);
// printf("u=%d x=%d y=%d w1=%lld w2=%lld
",u,x,y,w[i][j+1][1],w[i+1][j+1][0]);
}
}
for(int j=1;j<n;j++){
int u = j;
add(s,u,w[1][j+1][0]);
int v = j*(n-1);
add(t,v,w[j][n][1]);
}
dij(s);
if(d[t]>=inf64) printf("-1
");
else printf("%lld
",d[t]);
return 0;
}
/*
6 6
5 6 L 6
2 3 R 2
5 6 R 3
5 6 R 8
1 6 L 1
1 5 R 10
*/