Explanation of the second I interval of 2020 Niuke summer multi school training camp

2020 The second session of Niuke summer multi school training camp I Interval

The question ： For interval [l, r] There are two operations , The first is to reduce the interval , Turn it into [l+1,r] perhaps [l,r+1], The second is the expansion interval , Turn it into [l-1,r] perhaps [l,r+1], There are two blocking operations (l,r,dir,c), The first one is dir='L’ You can make [l,r] Don't become [l+1,r], The second kind dir='R’ You can make [l,r] Don't become [l,r-1], The cost is c. The starting point is [1,n], Make it impossible to reach during operation [i,i] In the form of , Ask what the minimum cost is .
solution ： First of all, this is a grid diagram , The starting point is the upper right corner , The end point is the point on the diagonal , To make the starting point unable to reach the end , Some blocking operations , It's equivalent to cutting off some edges , So how to build an edge for the example , Look at the picture .

3 4
1 3 L 10
1 3 R 3
1 2 L 1
1 2 R 1

In fact, it is to establish super source and super sink , Then the meaning of each edge is to cut off this edge , Up here s To t Just run the shortest way . The thought applied is the thought of minimum cut , A wolf catching a rabbit is very similar to this question , But it seems that the author of the question has lost the practice of seeking the minimum cut , I ISAP Constant segment error .

Code ：

#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;
}