Deliver the Cake

HDU – 6805 

It is Zhang3’s birthday! Zhang3 has bought a birthday cake and now it’s time to take it home.

There are nn villages, labeled 1,2,…,n1,2,…,n. There are mm bidirectional roads, the ithith of which connects village aiai, bibi and it is didi meter(s) long.

The bakery locates at village ss and Zhang3’s home locates at village tt. So Zhang3 wants to carry the cake from ss to tt. She can carry the cake either with her left hand or with her right hand. She can switch to the other hand during the trip, which takes extra xx second(s) each time (when she’s performing this action, she must stay in her place). Switching is allowed at any place, including the middle of the roads. She can do this as many times as she like, or don’t do it at all.

Some villages are LEFT. When Zhang3 is at a LEFT village, she must carry the cake with her left hand at the moment. In the same way, some other villages are RIGHT, she must carry with her right hand when she’s at these villages. The rest villages are called MIDDLE. There’s no special rules at MIDDLE villages.

Zhang3 can start and finish with any hand carrying the cake. However, if ss or tt is not MIDDLE, their special rules must be followed.

Please help Zhang3 find a way to take the cake home, with the minimum amount of spent time.
InputThe first line of the input gives the number of test cases, T(1≤T≤100)T(1≤T≤100). TT test cases follow.

For each test case, the first line contains five integers n,m,s,t,x(1≤n≤105,1≤m≤2×105,1≤x≤109)n,m,s,t,x(1≤n≤105,1≤m≤2×105,1≤x≤109), representing the number of villages, the number of roads, the bakery’s location, home’s location, and the time spent for each switching.

The next line contains a string of length nn, describing the type of each village. The ithith character is either LL representing village ii is LEFT, or MM representing MIDDLE, or RR representing RIGHT.

Finally, mm lines follow, the ithith of which contains three integers ai,bi,di(1≤di≤109)ai,bi,di(1≤di≤109), denoting a road connecting village aiai and bibi of length didi.

It is guaranteed that tt can be reached from ss.

The sum of nn in all test cases doesn’t exceed 2×1052×105. The sum of mm doesn’t exceed 4×1054×105.
OutputFor each test case, print a line with an integer, representing the minimum amount of spent time (in seconds).
Sample Input

1
3 3 1 3 100
LRM
1 2 10
2 3 10
1 3 100

Sample Output

100

---

思路：分层最短路。

如果不懂这个可以先去洛谷做下飞行路线

注意代码卡cin

参考博客： https://blog.csdn.net/njuptACMcxk/article/details/107701040

“

①、u和v的类型均为L或均为R：在u和v之间建一条权值为w的无向边。

 

②、u和v的类型一个为L，另一个为R：在u和v之间建一条权值为w+x的无向边。

 

③、u为L，v为M：在u和v之间建立权值为w的无向边，u和v+n之间建立权值为w+x的无向边。

 

④、u为M，v为L：在u和v之间建立权值为w的无向边，u+n和v之间建立权值为w+x的无向边。

 

⑤、u为R，v为M：在u和v之间建立权值为w+x的无向边，u和v+n之间建立权值为w的无向边。

 

⑥、u为M，v为R：在u和v之间建立权值为w+x的无向边，u+n和v之间建立权值为w的无向边。

 

⑦、u为M，v为M：

在u和v之间建立权值为w的无向边，u和v+n之间建立权值为w+x的无向边。

在u+n和v之间建立权值为w+x的无向边，u+n和v+n之间建立权值为w的无向边。

 

注意：

当起点或终点是M类型的点时，起点或终点会有两个。

 

此时可建立虚拟源点，与起点或终点之间连一条长度为0的边即可。

 

起点可以取0号虚拟源点，终点可取2n+1号虚拟源点(因为拆点将右点都增加了n的偏移量)。

”

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=3e5+100;
typedef long long LL;
typedef pair<LL,LL>P;///first最短距离,second顶点的编号 
struct edge{
	LL to,cost;
};
vector<edge>g[maxn];
bool vis[maxn];
char str[maxn];
LL dis[maxn];
LL n,m,start,final,sw;
void dijkstra()
{
    LL s=start;///起点是1
	memset(dis,0x3f,sizeof(dis));///初始化 
	if(str[s]=='M') dis[0]=0; 
	else dis[s]=0;
	memset(vis,0,sizeof(vis));///初始化 
	priority_queue< P, vector<P> , greater<P> >que;
	if(str[s]=='M') que.push({0,0});
	else que.push({0,s});
	while(!que.empty())
	{
		P p=que.top();que.pop();
		int v=p.second;
		if(vis[v]) continue;
		vis[v]=1;
		for(int i=0;i<g[v].size();i++)
		{
			edge e=g[v][i];
			if(dis[e.to]>dis[v]+e.cost)
			{
				dis[e.to]=dis[v]+e.cost;
				que.push({dis[e.to],e.to});	
			}	
		}	
	}
}
int main(void)
{

  int ti;scanf("%d",&ti);
 
  while(ti--)
  {	 
	 scanf("%lld%lld%lld%lld%lld",&n,&m,&start,&final,&sw);
	 for(int i=0;i<=2*n+1;i++) g[i].clear();
     scanf("%s",str+1);
  	 if(str[start]=='M'){
  	 	g[0].push_back({start,0});g[start].push_back({0,0});
		g[0].push_back({start+n,0});g[start+n].push_back({0,0});   	
	 }
	 if(str[final]=='M'){
	 	g[2*n+1].push_back({final,0});g[final].push_back({2*n+1,0});
	 	g[final+n].push_back({2*n+1,0});g[2*n+1].push_back({final+n,0});
	 }
	 while(m--)
	 {
	 	LL u,v,w;scanf("%lld%lld%lld",&u,&v,&w);
	 	if(str[u]=='L'&&str[v]=='R'||str[u]=='R'&&str[v]=='L'){
	 	  g[u].push_back({v,w+sw});g[v].push_back({u,w+sw});		 		
		}
	 	else if(str[u]=='L'&&str[v]=='L'){
	 		g[u].push_back({v,w});g[v].push_back({u,w});	
		}
		else if(str[u]=='R'&&str[v]=='R'){
			g[u].push_back({v,w});g[v].push_back({u,w});
		}
		else if(str[u]=='L'&&str[v]=='M'){
			g[u].push_back({v,w});g[v].push_back({u,w});
			g[u].push_back({v+n,sw+w});g[v+n].push_back({u,sw+w});
		}
		else if(str[u]=='M'&&str[v]=='L'){
			g[u].push_back({v,w});g[v].push_back({u,w});
			g[u+n].push_back({v,w+sw});g[v].push_back({u+n,w+sw});
		}
		else if(str[u]=='R'&&str[v]=='M'){
			g[u].push_back({v+n,w});g[v+n].push_back({u,w});
			g[u].push_back({v,w+sw});g[v].push_back({u,w+sw});
		}
		else if(str[u]=='M'&&str[v]=='R'){
			g[u+n].push_back({v,w});g[v].push_back({u+n,w});
			g[u].push_back({v,w+sw});g[v].push_back({u,w+sw});
		}
		else if(str[u]=='M'&&str[v]=='M'){
			g[u].push_back({v,w});g[v].push_back({u,w});
			g[u].push_back({v+n,w+sw});g[v+n].push_back({u,w+sw});
			g[u+n].push_back({v,w+sw});g[v].push_back({u+n,w+sw});
			g[u+n].push_back({v+n,w});g[v+n].push_back({u+n,w});
		}
	 }
	 dijkstra();
	 if(str[final]=='M') printf("%lld\n",dis[2*n+1]);
	 else printf("%lld\n",dis[final]);
  }
return 0;
}