最短路，链式向前星，循环dp，分层图

题意：

分析：

这题不难，循环dp问题而已(分层图)
正好最近我认真研究过，所以当时在赛场上的时候我还是很有自信能做出来的。

思路如下，我们添加一维构造循环dp。d[i][j]为节点i在j状态下距离s的最短距离！！！
我们很容易能推出其动态转移方程：
d[i][j] =
min(d[k][j] k为i邻节点，且k与i同类型或者为M)
min(d[k][(j+1)%2] k为i邻节点，且k与i类型相反或为M)
二者取小

很容易的发现这是个典型的循环dp，我们使用松弛操作对其进行破解。使用dijstra
具体原理请看我的另一篇博客：
https://blog.nowcoder.net/n/8316b13c345d49b08b2ae7f41c49da71

代码如下：

#include<iostream>
#include<algorithm>
#include<queue>
#include<cassert>
#include<string>
#include<functional>
#include<vector>
using namespace std;
typedef long long ll;
const ll max_n = 2e5 + 100;
const ll inf = 1e18;
typedef pair<int, int> pii;
typedef pair<ll, pii> pli;
struct edge {
    int to;
    ll cost;
    int next = false;
}E[4 * max_n];
string a;
ll d[max_n][2];
int n, m, s, e;
ll x;
char type[2] = { 'L','R' };
int cnt = 1;
ll head[max_n];

void add(ll from, ll to, ll w) {
    E[cnt].to = to;
    E[cnt].cost = w;
    E[cnt].next = head[from];
    head[from] = cnt++;
}

void dijstra(int s,int t) {
    for (int i = 1;i <= n;i++) d[i][0] = d[i][1] = inf;
    if (a[s - 1] == 'L' && t == 1)return;
    if (a[s - 1] == 'R' && t == 0)return;
    priority_queue<pli,vector<pli>,greater<pli>> que;
    d[s][t] = 0;que.push({ d[s][t],{s,t} });
    while (!que.empty()) {
        pli p = que.top();que.pop();
        pii pos = p.second;ll dist = p.first;
        if (dist > d[pos.first][pos.second]) continue;
        char ch = type[pos.second];
        for (int i = head[pos.first];i;i = E[i].next) {
            edge e = E[i];
            if (a[e.to - 1] == ch || a[e.to - 1] == 'M') {
                if (d[e.to][pos.second] > dist + e.cost) {
                    d[e.to][pos.second] = dist + e.cost;
                    que.push({ d[e.to][pos.second],{e.to,pos.second} });
                }
            }
            if (a[e.to - 1] != ch || a[e.to - 1] == 'M') {
                if (d[e.to][(pos.second + 1) & 1] > dist + e.cost + x) {
                    d[e.to][(pos.second + 1) & 1] = dist + e.cost + x;
                    que.push({ d[e.to][(pos.second + 1) & 1],{e.to,(pos.second + 1) & 1} });
                }
            }
        }
    }
}

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;
        for (int i = 0;i <= n;i++)
            head[i] = 0;
        cin >> a;
        for (int i = 1;i <= m;i++) {
            int u, v; ll w;
            cin >> u >> v >> w;
            add(u, v, w);
            add(v, u, w);
        }
        ll ans = inf;
        if (a[s - 1] == type[0] || a[s - 1] == 'M') {
            dijstra(s, 0);
            ll ans1 = min(d[e][1], d[e][0]);
            ans = min(ans, ans1);
        }
        if (a[s - 1] == type[1] || a[s - 1] == 'M') {
            dijstra(s, 1);
            ll ans1 = min(d[e][1], d[e][0]);
            ans = min(ans, ans1);
        }
        cout << ans << endl;
    }
}

当然，你也可以使用分层图，但我个人认为分层图并没有循环dp的想法系统直接

另外，这题卡vector我之前只会用vector。赛场上第一次用前向链式星，细节错了。真的可惜