传送门
这道题主要是建边麻烦，而稍微省点麻烦的就是拆点进行建边了，将所有 MMM 的点拆成左跟右，按部就班按照题目意思进行建边
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T>
inline void read(T &x)
{
int tmp = 1;char c = getchar();x = 0;while (c > '9' || c < '0'){
if (c == '-')tmp = -1;c = getchar();}while (c >= '0' && c <= '9'){
x = x * 10 + c - '0';c = getchar();}x *= tmp;
}
const int inf=0x3f3f3f3f;
const int mod=998244353;
const int N=1e5+10;
const int M=3e6+10;
int head[N<<1],cnt;
struct edge{
int next,to;ll w;
}e[M];
void add(int u,int v,ll w){
e[cnt].to=v;e[cnt].next=head[u];e[cnt].w=w;head[u]=cnt++;
}
int st,ed;
struct node{
int v;ll d;node(int v,ll d):v(v),d(d){
}bool friend operator<(const node &a,const node &b){
return a.d>b.d;}
};
bool vis[N<<1];
ll dijkstra(){
priority_queue<node>que;que.push(node(st,0));memset(vis,false,sizeof vis);while(!que.empty()){
node vn=que.top();que.pop();if(vn.v==ed){
return vn.d;}if(vis[vn.v]) continue;vis[vn.v]=1;int u=vn.v;for(int i=head[u];~i;i=e[i].next){
int v=e[i].to;if(vis[v]) continue;que.push(node(v,vn.d+e[i].w));}}
}
int n,m,s,t;ll x;
char s0[N];
int main(){
ios::sync_with_stdio(false);cin.tie(nullptr); cout.tie(nullptr);int T;read(T);while(T--){
memset(head,-1,sizeof head);cnt=0;read(n),read(m),read(s),read(t),read(x);scanf("%s",s0+1);for(int i=1;i<=m;++i){
int u,v;ll w;read(u),read(v),read(w);if(s0[u]=='M'&&s0[v]=='M'){
add(u<<1,v<<1,w);add(v<<1,u<<1,w);add(u<<1,v<<1|1,w+x);add(v<<1|1,u<<1,w+x);add(u<<1|1,v<<1,w+x);add(v<<1,u<<1|1,w+x);add(u<<1|1,v<<1|1,w);add(v<<1|1,u<<1|1,w);}else if(s0[u]=='L'&&s0[v]=='L'){
add(u<<1,v<<1,w);add(v<<1,u<<1,w);}else if(s0[u]=='L'&&s0[v]=='R'){
add(u<<1,v<<1|1,w+x);add(v<<1|1,u<<1,w+x);}else if(s0[u]=='L'&&s0[v]=='M'){
add(u<<1,v<<1,w);add(v<<1,u<<1,w);add(u<<1,v<<1|1,w+x);add(v<<1|1,u<<1,w+x);}else if(s0[u]=='M'&&s0[v]=='L'){
add(u<<1,v<<1,w);add(v<<1,u<<1,w);add(u<<1|1,v<<1,w+x);add(v<<1,u<<1|1,w+x);}else if(s0[u]=='M'&&s0[v]=='R'){
add(u<<1,v<<1|1,w+x);add(v<<1|1,u<<1,w+x);add(u<<1|1,v<<1|1,w);add(v<<1|1,u<<1|1,w);}else if(s0[u]=='R'&&s0[v]=='L'){
add(u<<1|1,v<<1,w+x);add(v<<1,u<<1|1,w+x);}else if(s0[u]=='R'&&s0[v]=='M'){
add(u<<1|1,v<<1,w+x);add(v<<1,u<<1|1,w+x);add(u<<1|1,v<<1|1,w);add(v<<1|1,u<<1|1,w);}else if(s0[u]=='R'&&s0[v]=='R'){
add(u<<1|1,v<<1|1,w);add(v<<1|1,u<<1|1,w);}}st=0;ed=1;if(s0[s]=='L') add(st,s<<1,0);else if(s0[s]=='R') add(st,s<<1|1,0);else{
add(st,s<<1,0);add(st,s<<1|1,0);}if(s0[t]=='L') add(t<<1,ed,0);else if(s0[t]=='R') add(t<<1|1,ed,0);else{
add(t<<1,ed,0);add(t<<1|1,ed,0);}printf("%lld\n",dijkstra());} return 0;
}