题解
可以发现，对于巡演的路线 (x o y) 和 (a o b)，若 (min(x,y) eq min(a,b)) 或 (max(x,y) eq max(a,b))，则其答案互不影响。不妨设 (x<y)，我们需要对每一种 ((x,y),(y,x)) 求出最小值。
将巡演路线中 (x o y) 记作 (()，(y o x) 记作 ())，则它形成了一个仅由左右括号组成的序列。设 (A) 为 (x o y) 的最优价钱，(B) 同理；(AB) 为 (x o y o x) 的最优价钱，(BA) 同理。则有：(A=min(operatorname{cost}(x o y),AB),AB=min(A+B,operatorname{cost}(x o y o x)))，(B,BA) 同理。
不妨设 (AB<BA)，于是，最优策略是：不断地删去括号序列中的 (()) 子序列（不必连续），然后不断地删去 ()() 子序列，直到只剩下若干 (() 或 ())。
若 (AB>BA)，则只需要将所有左、右括号调换，然后 (A,B) 调换，(AB,BA) 调换，再执行上面的策略即可。
注意 (max(AB,BA)) 可能会达到 (2 imes 10^9)，因此 (inf) 要开得大一点。
代码
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <utility>
#include <map>
#include <string>
#include <stack>
using namespace std;
#define For(Ti,Ta,Tb) for(int Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(int Ti=(Ta);Ti>=(Tb);--Ti)
template<typename T> void Read(T &_x){
_x=0;int _f=1;
char ch=getchar();
while(!isdigit(ch)) _f=(ch=='-'?-1:_f),ch=getchar();
while(isdigit(ch)) _x=_x*10+(ch^48),ch=getchar();
_x*=_f;
}
template<typename T,typename... Args> void Read(T &_x,Args& ...others){
Read(_x);Read(others...);
}
typedef long long ll;
typedef pair<int,int> pii;
const ll Inf=0x3f3f3f3f3fLL;
const int N=3e5+5;
int n,d,m;
map<pii,string> mp;
void Insert(int x,int y){
if(x<y) mp[{x,y}]+='A';
else mp[{y,x}]+='B';
}
map<pii,ll> one,two;
void Insert2(map<pii,ll> &fli,int u,int v,int p){
pii x(u,v);
if(!fli.count(x)) fli.insert({x,p});
else fli[x]=min(fli[x],ll(p));
}
ll Find(const map<pii,ll> &fli,int u,int v){
pii x(u,v);
if(!fli.count(x)) return Inf;
return fli.at(x);
}
int rem[N];
ll Calc(const string &s,ll cost,char c){
ll res=0;
stack<int> stk;
for(int i=0;i<int(s.size());++i){
if(rem[i]) continue;
if(s[i]==c) stk.push(i);
else{
if(stk.empty()) continue;
res+=cost,rem[stk.top()]=rem[i]=1;
stk.pop();
}
}
return res;
}
int main(){
Read(n,d);
int pre;
For(i,1,d){
int x;Read(x);
if(i>1) Insert(pre,x);
pre=x;
}
Read(m);
For(i,1,m){
int u,v,p;char temp[5];
Read(u,v);scanf("%s",temp);Read(p);
if(temp[0]=='O') Insert2(one,u,v,p);
else Insert2(two,u,v,p);
}
ll ans=0;
for(const auto &pr:mp){
int x=pr.first.first,y=pr.first.second;
string s=pr.second;
for(int i=0;i<int(s.size());++i) rem[i]=0;
ll A=Find(one,x,y),B=Find(one,y,x);
ll AB=Find(two,x,y),BA=Find(two,y,x);
A=min(A,AB),B=min(B,BA);
AB=min(AB,A+B),BA=min(BA,A+B);
if(BA<AB){
for(char &c:s){
if(c=='A') c='B';
else c='A';
}
swap(A,B);swap(AB,BA);
}
ans+=Calc(s,AB,'A');
ans+=Calc(s,BA,'B');
for(int i=0;i<int(s.size());++i){
if(rem[i]) continue;
if(s[i]=='A') ans+=A;
else ans+=B;
}
}
printf("%lld
",ans);
return 0;
}