HDU - 6805 Deliver the Cake（拆点+最短路）

传送门

这道题放了十几天了终于给补了，原来一直卡在数据范围，因为最多拆成$2e5$个点，那么最多$8e5$条边，因为用的前向星，那么需要再多两倍的空间，因此数组要开到$2e6$!
杭电那边一直给我报$TLE$，但是明明是$WA$或者$RE$的，真的烦

因为有$M$点的影响，那么我们可以考虑将每个$M$点拆成一个$L$点和一个$R$点，这样就在建图时麻烦一点，需要写$7$种情况特判，然后为了方便我们设置一个超级起点和超级终点，分别为$0,2\ast n-1$，权值设为$0$，这样一次最短路就跑出结果了

以下代码是前向星堆优化的迪杰斯特拉

#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define Vector Point
#define lowbit(x) (x&(-x))
#define mkp(x,y) make_pair(x,y)
#define mem(a,x) memset(a,x,sizeof a);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<ll,int> pii;
typedef pair<double,double> pdd;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const double dinf=1e300;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=4e5+10;
const int maxm=2e6+10;

struct node{
    int to,next;
    ll w;
};

ll cost;

struct Dijkstra{
    int n,tot;
    int head[maxn];
    ll d[maxn];
    node edge[maxm];

    void init(int n){
        this->n=n,tot=0;
        memset(head,0,sizeof head);
    }

    void addEdge(int u,int v,ll w){
        tot++;
        edge[tot].to=v;
        edge[tot].w=w;
        edge[tot].next=head[u];
        head[u]=tot;

        tot++;
        edge[tot].to=u;
        edge[tot].w=w;
        edge[tot].next=head[v];
        head[v]=tot;
    }

    ll dijkstra(int s,int e){
        priority_queue<pii,vector<pii>,greater<pii>> q;
        for(int i=0;i<=n;i++) d[i]=INF;
        d[s]=0;
        q.push({0,s});
        while(!q.empty()){
            pii cur=q.top();
            q.pop();
            int u=cur.second;
            //if(u==e) return d[e];
            if(cur.first!=d[u]) continue;
            for(int i=head[u];i;i=edge[i].next){
                int v=edge[i].to;
                ll w=edge[i].w;
                if(d[v]>d[u]+w){
                    d[v]=d[u]+w;
                    q.push(pii(d[v],v));
                }
            }
        }
        return d[e];
    }
}dj;

char sym[maxn];

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    //ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t,n,m,s,e;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d%d%lld",&n,&m,&s,&e,&cost);
        scanf("%s",sym+1);
        dj.init(2*n+1);
        for(int i=0,u,v,w;i<m;i++){
            scanf("%d%d%d",&u,&v,&w);
            if((sym[u]=='L' && sym[v]=='L') || (sym[u]=='R' && sym[v]=='R')){
                dj.addEdge(u,v,w);
            }else if((sym[u]=='L' && sym[v]=='R') || (sym[u]=='R' && sym[v]=='L')){
                dj.addEdge(u,v,cost+w);
            }else if(sym[u]=='L' && sym[v]=='M'){
                dj.addEdge(u,v,w);
                dj.addEdge(u,v+n,cost+w);
            }else if(sym[u]=='R' && sym[v]=='M'){
                dj.addEdge(u,v,cost+w);
                dj.addEdge(u,v+n,w);
            }else if(sym[u]=='M' && sym[v]=='L'){
                dj.addEdge(u,v,w);
                dj.addEdge(u+n,v,cost+w);
            }else if(sym[u]=='M' && sym[v]=='R'){
                dj.addEdge(u,v,cost+w);
                dj.addEdge(u+n,v,w);
            }else if(sym[u]=='M' && sym[v]=='M'){
                dj.addEdge(u,v,w);
                dj.addEdge(u,v+n,cost+w);
                dj.addEdge(u+n,v,cost+w);
                dj.addEdge(u+n,v+n,w);
            }
        }
        int ns=0,ne=2*n+1;
        if(sym[s]=='L' || sym[s]=='R'){
            dj.addEdge(ns,s,0);
        }else if(sym[s]=='M'){
            dj.addEdge(ns,s,0);
            dj.addEdge(ns,s+n,0);
        }
        if(sym[e]=='L' || sym[e]=='R'){
            dj.addEdge(e,ne,0);
        }else if(sym[e]=='M'){
            dj.addEdge(e,ne,0);
            dj.addEdge(e+n,ne,0);
        }
        printf("%lld\n",dj.dijkstra(ns,ne));
    }
    return 0;
}