传送门 这道题主要是建边麻烦，而稍微省点麻烦的就是拆点进行建边了，将所有 M M M 的点拆成左跟右，按部就班按照题目意思进行建边
#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; }