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。
连边：
- 若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的无向边。
注意：如果起点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*/
官方题解：
