这场打的很不好，可能是太久没有高强度做题了，思维绕不到关键的点上。最后被卡在1004，算是这次没打好的主要原因吧……我的锅。
Contest of Rope Pulling(01背包+随机化)
题意
Deliver the Cake(最短路+思维)
题意
求非负权无向图上最短路问题，每个点存在左手右手两种状态，当需要换手的时候会增加x单位时间，求最少用时。
思路
若图中某点a的限制为M，则将其拆成a1和a2代表L和R两个状态的点，并且a1和a2之间的成本为x。在进行连边的时候，如果两点状态确定(不是M)，那么直接(将x)加到他们之间的路径中；否则只将左右手一致的点连起来。
如abc三点状态为LMR，那么a-b1, b1-b2, b2-c。
``` c++
const int N = 1e6+10; const int M = 2e5+10;
int _, tot, ad;
int head[N], nex[N], edge[N], ver[N], vis[N];
ll dis[N], ans;
char chr[N];
// 注意所有dis均为long long
struct node {
ll dis;
int idx;
node(ll x, int y) {
dis = x, idx = y;
}
friend bool operator < (const node &A, const node &B){
return A.dis > B.dis; //大的先弹出
}
};
priority_queue< node > q;
void add(int x, int y, int z) {
ver[++tot] = y, edge[tot] = z, nex[tot] = head[x], head[x] = tot;
ver[++tot] = x, edge[tot] = z, nex[tot] = head[y], head[y] = tot;
}
ll dij(int s, int t) {
dis[s] = 0;
q.push( node(0, s) );
while(!q.empty()) {
int x = q.top().idx; q.pop();
if(vis[x]) continue;
vis[x] = 1;
for(int i = head[x]; ~i; i = nex[i]) {
int y = ver[i], z = edge[i];
if(dis[y] > dis[x] + z) {
dis[y] = dis[x] + z;
q.push( node(dis[y], y) );
}
}
}
return min(dis[t], dis[t + M]);
}
void init() {
tot = 0;
ms(head, -1);
ms(dis, inf), ms(vis, 0);
}
int main() {
int n, m, s, t;
for(scanf(“%d”, &_); _–; ) {
init();
scanf(“%d %d %d %d %d”, &n, &m, &s, &t, &ad);
scanf(“%s”, chr+1);
for1(i, n) if(chr[i] == ‘M’) add(i, i+M, ad);
for1(i, m) {
int x, y, z;
scanf(“%d %d %d”, &x, &y, &z);
if(chr[x] != ‘M’ && chr[y] != ‘M’) {
chr[x] == chr[y] ? add(x, y, z) : add(x, y, z+ad);
} else {
if(chr[x] == ‘M’ && chr[y] == ‘M’) {
add(x, y, z), add(x + M, y + M, z);
} else if(chr[x] != ‘M’) {
chr[x] == ‘L’ ? add(x, y, z) : add(x, y+M, z);
} else {
chr[y] == ‘L’ ? add(x, y, z) : add(x+M, y, z);
}
}
}
add(0, s, 0), add(0, s+M, 0);
ans = dij(0, t);
printf(“%lld\n”, ans);
}
}