url: https://www.luogu.com.cn/problem/P3110

tag:
USACO14DEC，最短路，bfs，USACO，2014

思路：
求三遍最短路，分别是正着求Bessie 和 Elsie 到每个点的最短路，和逆着求终点n到每个点的最短路，然后枚举看从哪个点开始一起走（Bessie 可以背着 Elsie 走）然后到终点的能量最小，更新ans。最后输出ans即可。

代码：

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
int B, E, P, n, m;
int idx, e[N], ne[N], h[N], w[N];
int distB[N], distE[N], distP[N];
bool st[N];
void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = 1;
    h[a] = idx ++;
}
void dijkstra(int s, int dist[])
{
    memset(st, 0, sizeof st);
    dist[s] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, s});

    while (!heap.empty())
    {
        auto t = heap.top();
        heap.pop();
        int ver = t.second;
        if (st[ver]) continue;
        st[ver] = true;
        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
}

int main()
{
    memset(h, -1, sizeof h);
    memset(distE, 0x3f, sizeof distE);
    memset(distB, 0x3f, sizeof distB);
    memset(distP, 0x3f, sizeof distP);
    cin >> B >> E >> P >> n >> m;
    for (int i = 0; i < m; i ++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    dijkstra(1, distB);
    dijkstra(2, distE);
    dijkstra(n, distP);
    int ans = 0x3f3f3f3f;
    for (int i = 1; i <= n; i ++)
    {
        ans = min(ans, B * distB[i] + E * distE[i] + P * distP[i]);
    }
    cout << ans;
    return 0;
}

url: https://www.luogu.com.cn/problem/P4667

tag:
BalticOI 2011，最短路，双端队列，bfs

思路：
用双端队列的bfs，每次走到下一步的时候判断方向是否相同，相同且更新之后路径变小就插到队列前面，不同且更新之后路径变小就插到队列后面。判断是否无解就判断一下终点横纵坐标和是否为奇数，为奇数就无解，因为起点和终点的横纵坐标奇偶性相同（沿对角线走）。
参考： https://www.luogu.com.cn/article/d1fliiql

代码：

#include <iostream>
#include <deque>
#include <cstring>
using namespace std;
const int N = 550;
const int dx[4] = {1, -1, -1, 1};
const int dy[4] = {1, 1, -1, -1};
const char a[5] = "\\/\\/";
const int ix[4] = {0, -1, -1, 0};
const int iy[4] = {0, 0, -1, -1};
deque<int> x;
deque<int> y;
int n, m;
char d[N][N];
int vis[N][N];

void bfs()
{
    memset(vis, 0x3f, sizeof vis);
    x.push_back(0);
    y.push_back(0);
    vis[0][0] = 0;
    while (!x.empty()) {
        int xx = x.front();
        int yy = y.front();
        x.pop_front();
        y.pop_front();
        for (int i = 0; i < 4; i++) {
            int dnx = xx + dx[i];
            int dny = yy + dy[i];
            int inx = xx + ix[i];
            int iny = yy + iy[i];
            if (dnx >= 0 && dnx <= n && dny >= 0 && dny <= m) {
                if (a[i] != d[inx][iny]) {
                    int t = vis[xx][yy] + 1;
                    if (t < vis[dnx][dny]) {
                        x.push_back(dnx);
                        y.push_back(dny);
                        vis[dnx][dny] = t;
                    }
                } else {
                    int t = vis[xx][yy];
                    if (t < vis[dnx][dny]) {
                        x.push_front(dnx);
                        y.push_front(dny);
                        vis[dnx][dny] = t;
                    }
                }
            }
        }
    }
    cout << vis[n][m] << endl;
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++) cin >> d[i];
    if ((n + m) % 2) cout << "NO SOLUTION" << endl;
    else bfs();
    return 0;
}

url: https://www.luogu.com.cn/problem/P1032

tag:
NOIP2002 提高组，字符串，bfs

思路：
因为是求最少的变换次数，所以可以用bfs。每次搜索都遍历字符串的每一个位置，将可以替换的地方都替换，然后判断是否出现过，没有出现过就加入队列。最后第一次出现字符串b的时候步数就是答案。

代码：

#include <iostream>
#include <queue>
#include <map>
#include <unordered_set>
using namespace std;

typedef pair<string, string> PSS;
typedef pair<string, int> PSI;

PSS mp[6];
string a, b;
queue<PSI> q;
unordered_set<string> st;
int idx = 0;

int bfs()
{
    q.push({a, 0});
    st.insert(a);

    while (!q.empty())
    {
        auto [current, step] = q.front(); q.pop();

        if (current == b) return step;

        if (step >= 10) continue;

        for (int i = 0; i < idx; i++)
        {
            string from = mp[i].first;
            string to = mp[i].second;
            size_t pos = current.find(from);
            while (pos != string::npos)
            {
                string newstr = current.substr(0, pos) + to + current.substr(pos + from.size());
                if (newstr.size() <= 20)
                {
                    if (!st.count(newstr))
                    {
                        st.insert(newstr);
                        q.push({newstr, step + 1});
                    }
                }
                pos = current.find(from, pos + 1);
            }
        }
    }
    return -1;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> a >> b;
    string c, d;
    while (cin >> c >> d)
    {
        if (!c.empty() && idx < 6)
        {
            mp[idx++] = {c, d};
        }
    }
    int res = bfs();

    if (res != -1 && res <= 10)
        cout << res;
    else
        cout << "NO ANSWER!";

    return 0;
}