杭电多校第四次自闭场，hdu6805 Deliver the Cake

题意

给n，m，s，t，k，分别表示村庄点数，双向路的个数，开始点，结束点，换手的时间，你的移速是1单位1s

第二行给一个长n的字符串，有LRM，分别表示左手，右手，随意。表示这个点经过的时候必须是左右手的规定

接下来m行，u，v，w，双向路径

思路

不看左右手，就是最短路，但是你如果加上左右手判断，就bfs找最短时间路径，加上特判。但是要考虑如果开始是M，结束也是M的时候，是开始左手好，还是结束左手好这种情况，所以要min（s->t最短路径，t->s最短路径）

就是这点导致我wa自闭，最后靠队友四题倒数下机了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<vector>
#include<map>
#include<functional>
#include<vector>
using namespace std;
#define ll long long
#define ull unsigned long long
#define il inline
#define it register int
#define inf 1e18
#define lowbit(x) (x)&(-x)
#define pii pair<int,int>
#define mak(n,m) make_pair(n,m)
#define mem(a,b) memset(a,b,sizeof(a))
#define mod 1000000007
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
const int N=2e5+10;
int n,m,tot,s,t,tt;
ll k;
int head[N];
ll dis[N],ans;
struct node{int to,next;ll w;}edge[N*2];
inline void add(int u,int v,ll w){
    edge[tot].to=v;edge[tot].w=w;
    edge[tot].next=head[u];head[u]=tot++;
}
char ss[N];
struct nn{
    int v,zy;ll dis;
    nn(){}
    nn(int vv,ll dd,int zz):v(vv),dis(dd),zy(zz){}
    friend bool operator<(const nn a,const nn b){
        return a.dis>b.dis;
    }
};
ll bfs(int xx,int yy){
    priority_queue<nn>q;
    int kk=0;
    if(ss[xx]=='L'){kk=-1;}
    else if(ss[xx]=='R'){kk=1;}
    q.push(nn(xx,0,kk));dis[xx]=0;
    while(!q.empty()){
        nn z=q.top();q.pop();
        if(z.v==yy){
            return z.dis;
        }
        for(int i=head[z.v];~i;i=edge[i].next){
            int v=edge[i].to;
            ll di=z.dis+edge[i].w;
            int k3=z.zy;
            if(ss[v]!='M'){
                if(ss[v]=='L' && z.zy==1){
                    di+=k;k3=-1;
                }
                else if(ss[v]=='R' && z.zy==-1){
                    di+=k;k3=1;
                }
                if(k3==0){
                    if(ss[v]=='L'){
                        k3=-1;
                    }
                    else if(ss[v]=='R'){
                        k3=1;
                    }
                }
            }
            if(dis[v]>=di){
                dis[v]=di;
                q.push(nn(v,di,k3));
            }
        }
    }
    return 0;
}
int main(){
    scanf("%d",&tt);
    while(tt--){
        tot=0;
        scanf("%d%d%d%d%lld",&n,&m,&s,&t,&k);
        for(int i=1;i<=n;i++){head[i]=-1;dis[i]=inf;}
        scanf("%s",ss+1);
        for(int i=0;i<m;i++){
            int v,w;
            ll l;
            scanf("%d%d%lld",&v,&w,&l);
            add(v,w,l);add(w,v,l);
        }
        if(s==t){
            printf("0
");continue;
        }
        ll ans=bfs(s,t);
         for(int i=1;i<=n;i++){dis[i]=inf;}
        printf("%lld
",min(ans,bfs(t,s)));
    }
    return 0;
}

不过我这个好像还挺快的-^-,多补题练练