2020杭電暑假多校第四場 1004. Deliver the Cake(最短路+拆點)

Deliver the Cake

題意

給出nm的無向圖，從st走向end，圖中點分為左中右三種要求，左的點要求經過時狀态必須為左，右同理，中則無特殊要求需求，出發選擇一種狀态，狀态切換需要額外花費x。問最小花費。

思路

易知進入中後，選擇的左或右狀态具有後效性。直接把中需求的點拆為左右兩個點即可。

代碼

比賽時候寫的太亂了=-=代碼以後改。

#include<bits/stdc++.h>
#define ll long long
#define INF 1e18
using namespace std;
const int maxn=2e6+10;
ll xx;
char zh[maxn];
struct Edge
{
    ll from,to,dist;
    Edge(ll f,ll t,ll d):from(f),to(t),dist(d){}
};

struct HeapNode
{
    ll d,u;
    HeapNode(ll d,ll u):d(d),u(u){}
    bool operator <(const HeapNode&rhs)const
    {
        return d>rhs.d;
    }
};
 
struct Dijkstra{
    int n,m;
    vector<Edge> edges;
    vector<int> G[maxn];
    bool done[maxn];
    ll d[maxn];
 
    void init(int n)
    {
        this->n=n;
        for(int i=0;i<n+5;i++) G[i].clear();
        edges.clear();
    }
 
    void AddEdge(ll from,ll to,ll dist)
    {
        edges.push_back(Edge(from,to,dist));
        m = edges.size();
        G[from].push_back(m-1);
    }
 
    ll dijkstra(int st,int ed){
        priority_queue<HeapNode> Q;
        for(int i=0;i<n*2+1000;i++) d[i]=INF;
        d[st]=d[st+n]=0;
        Q.push(HeapNode(d[st],st));//st也mid
        if(zh[st]=='M')Q.push(HeapNode(d[st+n],st+n));
        memset(done,0,sizeof(done));
        while(!Q.empty()){
            HeapNode x=Q.top(); Q.pop();
            int u=x.u;
            if(done[u]) continue;
            done[u]=true;
            char ty;
            if(u>n){
                ty='R';
                u=u-n;
            }
            else if(zh[u]=='M')ty='L';
            else ty='0';
            for(int i=0;i<G[u].size();i++){
                Edge &e=edges[G[u][i]];
                if(ty=='0'){
                    if(zh[e.to]=='M'){
                        int v1=e.to,v2=e.to+n;
                        ll l1=d[u]+e.dist,l2=d[u]+e.dist;
                        if(zh[u]=='L')l2+=xx;
                        else l1+=xx;
                        if(d[v1]>l1){
                            d[v1]=l1;
                            Q.push(HeapNode(d[v1],v1));
                        }
                        if(d[v2]>l2){
                            d[v2]=l2;
                            Q.push(HeapNode(d[v2],v2));
                        }
                    }
                    else{
                        int v1=e.to;
                        ll l1=d[u]+e.dist;
                        if(zh[v1]!=zh[u])l1+=xx;
                        if(d[v1]>l1){
                            d[v1]=l1;
                            Q.push(HeapNode(d[v1],v1));
                        }
                    }
                }
                else{
                    if(zh[e.to]=='M'){
                        int v1=e.to;
                        if(ty=='R')v1+=n;
                        ll l1=d[u]+e.dist;
                        if(ty=='R')l1=d[u+n]+e.dist;
                        if(d[v1]>l1){
                            d[v1]=l1;
                            Q.push(HeapNode(d[v1],v1));
                        }
                    }
                    else{
                        int v1=e.to;
                        ll l1=d[u]+e.dist;
                        if(ty=='R')l1=d[u+n]+e.dist;
                        if(zh[v1]!=ty)l1+=xx;
                        if(d[v1]>l1){
                            d[v1]=l1;
                            Q.push(HeapNode(d[v1],v1));
                        }
                    }
                }
            }
        }
        return min(d[ed-1],d[ed-1+n]);
    }
}DJ,AJ;
void Slove(){
    int n,m,st,ed;
    scanf("%d%d%d%d%lld",&n,&m,&st,&ed,&xx);
    DJ.init(n*2+5);
    scanf("%s",zh);
    for(int i=0;i<m;i++){
        int u,v;
        ll d;
        scanf("%d%d%lld",&u,&v,&d);
        u--,v--;
        DJ.AddEdge(u,v,d);
        DJ.AddEdge(v,u,d);
    }
    ll ans=DJ.dijkstra(ed-1,st);
    printf("%lld\n",ans);
}

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        Slove();
    }
    return 0;
}