题意
给出一个nm的无向图，有边权。
张三在起点s，目标是t。
点分成左点右点和中间点，到左点的时候必须用左手，到右点的时候必须用右手，中间点没有特殊要求。
张三每次切换左右手都要花费额外的时间，询问起点到终点的最短路。
题解
把每个点拆成两个点，左点拆成两个左点，右点拆成两个右点，中间点拆成一左一右两个点，然后跑dijsktra。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=4e5+10; const ll inf=1e18; int n,m,s,t,cost; string ss; struct node { int u; int v; int w; int next; }edge[maxn*8]; int head[maxn*3]; int tol=0; void addedge (int u,int v,int w) { edge[tol].u=u; edge[tol].v=v; edge[tol].w=w; edge[tol].next=head[u]; head[u]=tol++; edge[tol].u=v; edge[tol].v=u; edge[tol].w=w; edge[tol].next=head[v]; head[v]=tol++; } ll d[maxn]; int visit[maxn]; char wjm[maxn]; struct qnode { int v; ll w; bool operator < (const qnode &r) const { return w>r.w; } }; void dij (int s) { memset(visit,0,sizeof(visit)); for (int i=1;i<=2*n;i++) d[i]=inf; priority_queue<qnode> q; d[s]=0; q.push({s,0}); qnode tmp; while (!q.empty()) { tmp=q.top(); q.pop(); int u=tmp.v; if (visit[u]) continue; visit[u]=1; for (int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; int tt; if (wjm[u]==wjm[v]) tt=0; else tt=1; if (!visit[v]&&d[v]>d[u]+edge[i].w+tt*cost) { d[v]=d[u]+edge[i].w+tt*cost; //if (!visit[v]) { q.push({v,d[v]}); //visit[v]=1; //} } } } } int main () { int T; scanf("%d",&T); while (T--) { scanf("%d%d%d%d%d",&n,&m,&s,&t,&cost); for (int i=1;i<=n*2;i++) head[i]=-1; cin>>ss; //每个点拆成两个点 //l点拆成两个L //R点拆成两个R //M点拆成一个L一个R for (int i=1;i<=n;i++) { if (ss[i-1]=='L') { wjm[i]='L'; wjm[i+n]='L'; } else if (ss[i-1]=='R') { wjm[i]='R'; wjm[i+n]='R'; } else { wjm[i]='L'; wjm[i+n]='R'; } } tol=0; for (int i=0;i<m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); addedge(u,v,w); addedge(u+n,v,w); addedge(u+n,v+n,w); addedge(u,v+n,w); } ll ans=1e18; dij(s); ans=min(ans,d[t]); ans=min(ans,d[t+n]); dij(s+n); ans=min(ans,d[t]); ans=min(ans,d[t+n]); printf("%lld ",ans); } return 0; }