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

题目大意

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

解题思路

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

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

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

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

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

这样就相当于多加了边。

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

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

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

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

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

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

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#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;
}
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • © 2015-2021 sakurakarma
  • Powered by Hexo Theme Ayer
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信