2020 Multi-University Training Contest 4 D / HDU 6805 - Deliver the Cake

题目：Deliver the Cake
题意概述： 给你一张无向联通图，图中的结点属于三种类型中的一种，这三种类型分别为M,L,R。从L/R结点到R/L结点要多花费x的时间，求从s点到t点最少要花费多少时间。

分析：因为图中的每个结点都有一种状态，特别是M这种状态将带来经过同一条路可能有不同得状态变化(例如图： L->M->R，从1号点到2号点时将有两种选择第一种是L->M时不改变状态,第二种时L->M时将从L状态改变为R状态)
这种多选择得情况给我们跑最短路带来了很大的麻烦。因此我们考虑将M这种结点分为两个结点，这两个结点得状态分别为L，R。

连边：

1. 若u和v结点状态同时为L或R： 在u和v之间连一条权值为w的无向边。
2. 若u为L，v为R: 在u和v之间连一条权值为w+x的无向边。
3. 若v为L，u为R: 在u和v之间连一条权值为w+x的无向边。
4. 若u为L，u为M: 在u和v之间连一条权值为w的无向边。同时在u和v+n之间连一条权值为w+x的无向边。(v为L，v+n为R)
5. 若u为M，v为L: 在u和v之间连一条权值为w的无向边。同时在u+n和v之间连一条权值为w+x的无向边。
6. 若u为R，u为M: 在u和v之间连一条权值为w+x的无向边。同时在u和v+n之间连一条权值为w的无向边。
7. 若u为M，u为R: 在u和v之间连一条权值为w+x的无向边。同时在u+n和v之间连一条权值为w的无向边。
8. 若u为M，u为M: 在u和v之间连一条权值为w的无向边。 在u+n和v+n之间连一条权值为w的无向边。在u+n和v之间连一条权值为w+x的无向边。在u和v+n之间连一条权值为w+x的无向边。

注意：如果起点s为M，那么分点后将产生两个点，这样就有两个起点了，终点s同理。我们可以加一个结点0号点，将0号点与两个起点都连一条权值为0的无向边，再把0号点看成起点。同例我们可以加一个结点2n+1号点，将2n+1号点与两个终点都连一条权值为0的无向边，再把2*n+1号点看成终点。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int N=2e5+10;
typedef struct Edge{int to;ll cost;
}Edge;
typedef pair<ll,int> P;
vector<Edge> E[N];
ll dis[N];
char f[N];
void Init(int n){     //初始化for(int i=0;i<=2*n+5;i++){dis[i]=INF;E[i].clear();}
}
int main(){int T;scanf("%d",&T);while(T--){int n,m,s,t,x;scanf("%d %d %d %d %d",&n,&m,&s,&t,&x);scanf("%s",f+1);Init(n);for(int i=1;i<=m;i++){ //建边int t1,t2; ll t3;scanf("%d %d %lld",&t1,&t2,&t3);if(f[t1]==f[t2]&&(f[t1]=='L'||f[t2]=='R')){E[t1].push_back((Edge){t2,t3}); E[t2].push_back((Edge){t1,t3});}else if(f[t1]!=f[t2]&&f[t1]!='M'&&f[t2]!='M'){E[t1].push_back((Edge){t2,t3+x}); E[t2].push_back((Edge){t1,t3+x});}else if(f[t1]=='L'&&f[t2]=='M'){E[t1].push_back((Edge){t2,t3}); E[t2].push_back((Edge){t1,t3});E[t1].push_back((Edge){t2+n,t3+x}); E[t2+n].push_back((Edge){t1,t3+x});}else if(f[t1]=='M'&&f[t2]=='L'){E[t1].push_back((Edge){t2,t3}); E[t2].push_back((Edge){t1,t3});E[t1+n].push_back((Edge){t2,t3+x}); E[t2].push_back((Edge){t1+n,t3+x});}else if(f[t1]=='R'&&f[t2]=='M'){E[t1].push_back((Edge){t2,t3+x}),E[t2].push_back((Edge){t1,t3+x});E[t1].push_back((Edge){t2+n,t3}),E[t2+n].push_back((Edge){t1,t3});}else if(f[t1]=='M'&&f[t2]=='R'){E[t1].push_back((Edge){t2,t3+x}),E[t2].push_back((Edge){t1,t3+x});E[t1+n].push_back((Edge){t2,t3}),E[t2].push_back((Edge){t1+n,t3});}else{E[t1].push_back((Edge){t2,t3}); E[t2].push_back((Edge){t1,t3});E[t1+n].push_back((Edge){t2+n,t3}); E[t2+n].push_back((Edge){t1+n,t3});E[t1+n].push_back((Edge){t2,t3+x}); E[t2].push_back((Edge){t1+n,t3+x});E[t1].push_back((Edge){t2+n,t3+x}); E[t2+n].push_back((Edge){t1,t3+x});}}if(f[s]=='M'){   //如果s为M,则加一个0号结点，此时0号点为起点了E[0].push_back((Edge){s,0}),E[s].push_back((Edge){0,0});E[0].push_back((Edge){s+n,0}),E[s+n].push_back((Edge){0,0});}if(f[t]=='M'){  //如果t为M，则加个2*n+1号结点，此时2*n+1号点为起点了E[2*n+1].push_back((Edge){t,0}),E[t].push_back((Edge){2*n+1,0});E[2*n+1].push_back((Edge){t+n,0}),E[t+n].push_back((Edge){2*n+1,0});}//跑遍dijkstrapriority_queue<P,vector<P>,greater<P> > que; if(f[s]!='M'){que.push(P(0,s));dis[s]=0;}else{que.push(P(0,0));dis[0]=0;} while(!que.empty()){P p=que.top(); que.pop();int k=p.second;if(p.first>dis[k]) continue;for(int i=0;i<E[k].size();i++){Edge e=E[k][i];if(dis[e.to]>dis[k]+e.cost){dis[e.to]=dis[k]+e.cost;que.push(P(dis[e.to],e.to));}}}if(f[t]!='M')printf("%lld\n",dis[t]);else printf("%lld\n",dis[2*n+1]);}return 0;
}  
/*
1
3 3 1 3 0
LLL
1 2 1
1 3 1
2 3 1
output: 11
4 4 1 4 100
MLRM
1 2 10
1 3 10
3 4 10
2 4 10output: 201
4 4 1 4 100
LLRM
1 2 10
1 3 10
2 4 100
3 4 10output: 1101
5 7 1 5 100
LMLRR
1 2 10
1 3 100
2 4 20
2 3 10
3 4 30
2 5 10
4 5 100output: 1201
5 7 1 5 100
LMLRR
1 2 10
1 3 100
2 4 20
2 3 10
3 4 30
3 5 10
4 5 100output 130 1
3 3 1 3 40
LRM
1 2 10
2 3 10
1 3 100
output 60*/

官方题解：