题意:
有n个点，m条边的无向带权图，每一个点都有一个字母类型，每个点的类型有三种L,R,M。
L能转R，R转L，且需要花费x。
从L结点到R结点需要多花费x(要转换)，L或R结点到M结点，M结点可以为R结点也可以为L结点，所以 在进过M结点时你要选择是变R还是L。
所以要进行拆点。
注意: 当起点为M时，你需要增加一个0结点，连接到起点拆分之后的两个结点。当终点为M时，同理增加一个2*n+1结点连接终点拆分之后的两个结点。
拆分:
若u和v结点状态同时为L或R： 在u和v之间连一条权值为w的无向边。
若u为L，v为R: 在u和v之间连一条权值为w+x的无向边。
若v为L，u为R: 在u和v之间连一条权值为w+x的无向边。
若u为L，u为M: 在u和v之间连一条权值为w的无向边。同时在u和v+n之间连一条权值为w+x的无向边。(v为L，v+n为R)
若u为M，v为L: 在u和v之间连一条权值为w的无向边。同时在u+n和v之间连一条权值为w+x的无向边。
若u为R，u为M: 在u和v之间连一条权值为w+x的无向边。同时在u和v+n之间连一条权值为w的无向边。
若u为M，u为R: 在u和v之间连一条权值为w+x的无向边。同时在u+n和v之间连一条权值为w的无向边。
若u为M，u为M: 在u和v之间连一条权值为w的无向边。 在u+n和v+n之间连一条权值为w的无向边。在u+n和v之间连一条权值为w+x的无向边。在u和v+n之间连一条权值为w+x的无向边。
代码:
#include <bits/stdc++.h>#define ll long long
using namespace std;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int N=1e5+1;
typedef struct Edge{int to;ll value;}ed;
struct s1
{int q1;int we;friend bool operator <(s1 z,s1 x){return z.we>x.we;}
};
vector<ed> e[N];
int dis[100001];
int visit[100001];
char f[N];
void djstl(int s,int t,int n)
{int qd=0;if(f[s]=='M') dis[0]=0,qd=0;else dis[s]=0,qd=s;priority_queue<s1>qq;s1 node;node.q1=qd;node.we=dis[qd];qq.push(node);visit[qd]=1;while(!qq.empty()){node=qq.top();qq.pop();qd=node.q1;visit[qd]=1;for (int i=0;i<e[qd].size();i++){ed edg=e[qd][i];if(dis[edg.to]>dis[qd]+edg.value&&!visit[edg.to]){dis[edg.to]=dis[qd]+edg.value;node.q1=edg.to;node.we=dis[edg.to];qq.push(node);}}node=qq.top();while(visit[node.q1]&&!qq.empty()) qq.pop(),node=qq.top();}if(f[t]=='M') cout<<dis[2*n+1];else cout<<dis[t];
}
int main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int t;cin>>t;while(t--){int n,m,s,t,x;cin>>n>>m>>s>>t>>x;scanf("%s",f+1);for (int i=0;i<=2*n+1;i++) dis[i]=INF,visit[i]=0,e[i].clear();if(f[s]=='M'){e[s].push_back(ed{0,0});e[s+n].push_back(ed{0,0});e[0].push_back(ed{s,0});e[0].push_back(ed{s+n,0});}if(f[t]=='M'){e[t].push_back(ed{2*n+1,0});e[t+n].push_back(ed{2*n+1,0});e[2*n+1].push_back(ed{t,0});e[2*n+1].push_back(ed{t+n,0});}for (int i=0;i<m;i++){int a,b,d;cin>>a>>b>>d;if((f[a]=='L'&&f[b]=='L')||(f[a]=='R'&&f[b]=='R')){e[a].push_back(ed{b,d});e[b].push_back(ed{a,d});}if((f[a]=='L'&&f[b]=='R')||(f[a]=='R'&&f[b]=='L')){e[a].push_back(ed{b,d+x});e[b].push_back(ed{a,d+x});}if(f[a]=='L'&&f[b]=='M'){e[a].push_back(ed{b,d});e[a].push_back(ed{b+n,d+x});e[b].push_back(ed{a,d});e[b+n].push_back(ed{a,d+x});}if(f[a]=='R'&&f[b]=='M'){e[a].push_back(ed{b,d+x});e[a].push_back(ed{b+n,d});e[b].push_back(ed{a,d+x});e[b+n].push_back(ed{a,d});}if(f[a]=='M'&&f[b]=='L'){e[b].push_back(ed{a,d});e[b].push_back(ed{a+n,d+x});e[a].push_back(ed{b,d});e[a+n].push_back(ed{b,d+x});}if(f[a]=='M'&&f[b]=='R'){e[b].push_back(ed{a,d+x});e[b].push_back(ed{a+n,d});e[a].push_back(ed{b,d+x});e[a+n].push_back(ed{b,d});}if(f[a]=='M'&&f[b]=='M'){e[b].push_back(ed{a,d});e[b].push_back(ed{a+n,d+x});e[b+n].push_back(ed{a,d+x});e[b+n].push_back(ed{a+n,d});e[a].push_back(ed{b,d});e[a].push_back(ed{b+n,d+x});e[a+n].push_back(ed{b,d+x});e[a+n].push_back(ed{b+n,d});}}djstl(s,t,n);cout<<endl;}}