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});
}
//跑遍dijkstra
priority_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: 1 1 4 4 1 4 100 MLRM 1 2 10 1 3 10 3 4 10 2 4 10 output: 20 1 4 4 1 4 100 LLRM 1 2 10 1 3 10 2 4 100 3 4 10 output: 110 1 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 100 output: 120 1 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 100 output 130 1 3 3 1 3 40 LRM 1 2 10 2 3 10 1 3 100 output 60 */
官方题解：
京公网安备 11010502036488号