杭电多校第四场 1004 Deliver the Cake 题解

题目大意

给你一个n个点m条边的双向图，告诉你起点和终点，以及每个点对左右手的要求，如果是M的话，则既可以左手，又可以右手，但是交换手是需要时间的，求起点到终点的最短距离。

解题思路

这题比赛的时候毫无思路。

结束的时候直接看的题解。

没做过这种题的真的写的出吗。。

这个拆点的想法也太神奇了吧。

对于M的点，我们可以把i点当做是用左手，i+n当做是用右手。

这样就相当于多加了边。

如果是从不同的手切换来的，边的权值就等于原本路的权值加上换手的权值。

相同的话，就等于原本路的权值。

需要注意，如果起点和终点是M的话，就会出现两个起点和终点。

可以令0和$2n+1$作为真正的起点和终点。

只是需要在原本的基础上，加上0到两个起点，和$2n+1$到两个终点的边即可。

（找了一下午bug。。结果发现是return0在while循环里面。。吐了。。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int N = 2e5 + 10, M = 2e6 + 10;
const ll INF = 1e18;
int head[N], vis[N], n, m, s, e, x, cnt;
ll dis[N];
char str[N];

struct {
    int to, next, val;
}Map[M];
struct node {
    int v;
    ll c;
    node(int a = 0, ll b = 0) :v(a), c(b) {};
    bool operator <(const node& a) const { return c > a.c; }
};

void build(int u, int v, int val) {
    Map[cnt].to = v, Map[cnt].val = val;
    Map[cnt].next = head[u], head[u] = cnt++;
}

ll Dijkstra() {
    memset(vis, 0, sizeof(vis));
    memset(dis, 0x3f, sizeof(dis));
    priority_queue<node>q;
    if (str[s] == 'M') dis[0] = 0,q.push(node(0, 0));
    else dis[s] = 0,q.push(node(s, 0));
    node t;
    while (!q.empty()) {
        t = q.top();
        q.pop();
        int u = t.v;
        if (vis[u])    continue;
        vis[u] = 1;
        for (int i = head[u]; ~i; i = Map[i].next) {
            int v = Map[i].to, c = Map[i].val;
            if (!vis[v] && dis[v] > dis[u] + c)
                dis[v] = dis[u] + c, q.push(node(v, dis[v]));
        }
    }
    if (str[e] == 'M')    return dis[2 * n + 1];
    return dis[e];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while (t--) {
        cin >> n >> m >> s >> e >> x >> str + 1;
        memset(head, -1, sizeof(head)), cnt = 0;
        if (str[s] == 'M') {
            build(0, s, 0), build(s, 0, 0);
            build(0, s + n, 0), build(s + n, 0, 0);
        }
        if (str[e] == 'M') {
            build(e, 2 * n + 1, 0), build(2 * n + 1, e, 0);
            build(e + n, 2 * n + 1, 0), build(2 * n + 1, e + n, 0);
        }
        for (int i = 1; i <= m; i++) {
            int u, v, c;
            cin >> u >> v >> c;
            if ((str[u] == 'L' && str[v] == 'R') || (str[u] == 'R' && str[v] == 'L'))
                build(u, v, c + x), build(v, u, c + x);
            if ((str[u] == 'L' && str[v] == 'L') || (str[u] == 'R' && str[v] == 'R'))
                build(u, v, c), build(v, u, c);
            if (str[u] == 'L' && str[v] == 'M') {
                build(u, v, c), build(u, v + n, c + x);
                build(v, u, c), build(v + n, u, c + x);
            }
            if (str[u] == 'M' && str[v] == 'L') {
                swap(u, v);
                build(u, v, c), build(u, v + n, c + x);
                build(v, u, c), build(v + n, u, c + x);
            }
            if (str[u] == 'R' && str[v] == 'M') {
                build(u, v, c + x), build(u, v + n, c);
                build(v, u, c + x), build(v + n, u, c);
            }
            if (str[u] == 'M' && str[v] == 'R') {
                swap(u, v);
                build(u, v, c + x), build(u, v + n, c);
                build(v, u, c + x), build(v + n, u, c);
            }
            if (str[u] == 'M' && str[v] == 'M') {
                build(u, v, c), build(u, v + n, c + x), build(u + n, v, c + x), build(u + n, v + n, c);
                swap(u, v);
                build(u, v, c), build(u, v + n, c + x), build(u + n, v, c + x), build(u + n, v + n, c);
            }
        }
        cout << Dijkstra() << endl;
    }
    return 0;
}