#include <iostream>
#include <queue>
#include <unordered_map>
#include <algorithm>
using namespace std;

typedef pair<int, string> PIS;

int f(string state)
{
    int res = 0;
    for (int i = 0; i < 9; ++i)
    {
        if (state[i] != 'x')
        {
            int t = state[i] - '1';
            res += abs(t / 3 - i / 3) + abs(t % 3 - i % 3);
        }
    }
    return res;
}
string astar(string start, string end)
{
    char op[5] = {"udlr"};
    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};
    unordered_map<string, int> dist;
    unordered_map<string, pair<char, string>> prev;
    priority_queue<PIS, vector<PIS>, greater<PIS>> heap;
    heap.push({f(start), start});

    while (!heap.empty())
    {
        PIS t = heap.top();
        heap.pop();

        string state = t.second;

        if (state == end) break;
        int x, y;
        for (int i = 0; i < 9; ++i)
        {
            if (state[i] == 'x')
            {
                x = i / 3, y = i % 3;
                break;
            }
        }

        for (int i = 0; i < 4; ++i)
        {
            int a = x + dx[i], b = y + dy[i];
            if (a < 0 || a >= 3 || b < 0 || b >= 3) continue;

            string temp = state;
            swap(temp[a * 3 + b], temp[x * 3 + y]);

            int d = dist[state] + 1;
            if (!dist.count(temp) || dist[temp] > d)
            {
                dist[temp] = d;
                prev[temp] = {op[i], state};
                heap.push({dist[temp] + f(temp), temp});
            }
        }
    }
    string path;
    while (start != end)
    {
        path += prev[end].first;
        end = prev[end].second;
    }
    reverse(path.begin(), path.end());
    return path;
}
int main()
{
    string start, x, seq;
    while (cin >> x)
    {
        start += x;
        if (x != "x") seq += x;
    }
    string end = "12345678x";
    int t = 0;
    for (int i = 0; i < 8; ++i)
        for (int j = i + 1; j < 8; ++j)
            if (seq[i] < seq[j])
                ++t;
    if (t & 1) puts("unsolvable");
    else cout << astar(start, end) << endl;
    return 0;
}

易知，当点 $x$ 第 $k$ 次从优先队列队头取出时，求得的就是从起点到点 $x$ 的第 $k$ 短路代价

直接用优先队列做的时间复杂度为 $O(K(N + M) \log (N + M))$

考虑设计估价函数 f(x) 为 x 到点 T 的最短路距离

这样在第 K 短路中，点x 到点T的估计距离f(x)小于实际距离，估价函数设计成立

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;
typedef pair<int, PII> PIII;

const int N = 1010, M = 20010;

int S, T, K, n, m;
int hp[N], hn[N], e[M], w[M], ne[M], idx;
int cnt[N], dist[N];
bool st[N];

void add(int h[], int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
void dijkstra()
{
    memset(st, 0, sizeof st);
    memset(dist, 0x3f, sizeof dist);
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    dist[T] = 0;
    heap.push({0, T});
    while (heap.size())
    {
        PII t = heap.top(); heap.pop();

        if (st[t.y]) continue;
        st[t.y] = true;

        for (int i = hn[t.y]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t.y] + w[i])
            {
                dist[j] = dist[t.y] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
}
int f(int id)
{
    return dist[id];
}
int astar()
{
    memset(cnt, 0, sizeof cnt);
    priority_queue<PIII, vector<PIII>, greater<PIII>> heap;
    heap.push({f(S), {0, S}});
    while (heap.size())
    {
        PIII t = heap.top(); heap.pop();

        int ver = t.y.y, d = t.y.x;
        cnt[ver] ++ ;
        if (cnt[T] == K) return d;

        for (int i = hp[ver]; ~i; i = ne[i])
        {
            int j = e[i];
            if (cnt[j] < K)
                heap.push({d + w[i] + f(j), {d + w[i], j}});
        }
    }
    return -1;
}
int main()
{
    cin >> n >> m;
    memset(hp, -1, sizeof hp);
    memset(hn, -1, sizeof hn);
    while (m -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(hp, a, b, c);
        add(hn, b, a, c);
    }
    cin >> S >> T >> K;
    if (S == T) K ++ ;

    dijkstra();
    cout << astar() << endl;
    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 810;

int n, m;
char g[N][N];
int st[N][N];
PII boy, girl, ghost[2];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

bool check(int a, int b, int t)
{
    if (a < 0 || a >= n || b < 0 || b >= m || g[a][b] == 'X') return false;
    for (int i = 0; i < 2; i ++ )
        if (abs(ghost[i].x - a) + abs(ghost[i].y - b) <= 2 * t)
            return false;
    return true;
}
int solve()
{
    memset(st, 0, sizeof st);
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ) cin >> g[i];
    int cnt = 0;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            if (g[i][j] == 'M') boy = {i, j};
            else if (g[i][j] == 'G') girl = {i, j};
            else if (g[i][j] == 'Z') ghost[cnt ++ ] = {i, j};

    queue<PII> qb, qg;
    qb.push(boy);
    qg.push(girl);

    int step = 0;
    while (qb.size() || qg.size())
    {
        step ++ ;
        for (int i = 0; i < 3; i ++ )
        {
            for (int j = 0, siz = qb.size(); j < siz; j ++ )
            {
                PII t = qb.front(); qb.pop();
                int x = t.x, y = t.y;
                if (!check(x, y, step)) continue;
                for (int k = 0; k < 4; k ++ )
                {
                    int a = x + dx[k], b = y + dy[k];
                    if (check(a, b, step))
                    {
                        if (st[a][b] == 2) return step;
                        if (!st[a][b])
                        {
                            st[a][b] = 1;
                            qb.push({a, b});
                        }
                    }
                }
            }
        }
        for (int i = 0; i < 1; i ++ )
        {
            for (int j = 0, siz = qg.size(); j < siz; j ++ )
            {
                PII t = qg.front(); qg.pop();
                int x = t.x, y = t.y;
                if (!check(x, y, step)) continue;
                for (int k = 0; k < 4; k ++ )
                {
                    int a = x + dx[k], b = y + dy[k];
                    if (check(a, b, step))
                    {
                        if (st[a][b] == 1) return step;
                        if (!st[a][b])
                        {
                            st[a][b] = 2;
                            qg.push({a, b});
                        }
                    }
                }
            }
        }
    }
    return -1;
}
int main()
{
    int T;
    cin >> T;
    while (T -- ) cout << solve() << endl;
    return 0;
}

直接拆点，以二元组 {city, fuel} 作为一个点，进行建图，然后做一遍最短路即可

每一次扩展有两种选择：

1. 当前油箱未满，且加一升油后 {city, fuel} + price[city] < {city, fuel + 1} 那么就在当前城市加一升油，并扩展出去
2. 当前油量可以抵达下一个城市且 cost < {next, fuel - dist} 那就扩展出去

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;
typedef pair<int, PII> PIII;

const int INF = 0x3f3f3f3f;

int n, m, q;
int C, S, E;
int h[1010], e[20010], w[20010], ne[20010], idx;
int p[1010];
int dist[1010][110];
bool st[1010][110];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int dijkstra()
{
    memset(st, 0, sizeof st);
    memset(dist, 0x3f, sizeof dist);
    priority_queue<PIII, vector<PIII>, greater<PIII>> heap;
    dist[S][0] = 0;
    heap.push({0, {S, 0}});
    while (heap.size())
    {
        auto t = heap.top(); heap.pop();
        int cost = t.x, ver = t.y.x, fuel = t.y.y;

        if (st[ver][fuel]) continue;
        st[ver][fuel] = true;
        if (ver == E) return cost;

        if (fuel < C && dist[ver][fuel + 1] > cost + p[ver])
        {
            dist[ver][fuel + 1] = cost + p[ver];
            heap.push({cost + p[ver], {ver, fuel + 1}});
        }
        for (int i = h[ver]; ~i; i = ne[i])
        {
            int j = e[i], d = w[i];
            if (fuel >= d && dist[j][fuel - d] > cost)
            {
                dist[j][fuel - d] = cost;
                heap.push({cost, {j, fuel - d}});
            }
        }
    }
    return -1;
}
int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ) cin >> p[i];
    for (int i = 0; i < m; i ++ )
    {
        int u, v, d;
        cin >> u >> v >> d;
        add(u, v, d), add(v, u, d);
    }
    cin >> q;
    while (q -- )
    {
        cin >> C >> S >> E;
        int t = dijkstra();
        if (~t) cout << t << endl;
        else puts("impossible");
    }
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>

#define x first
#define y second

using namespace std;

typedef pair<int,int> PII;

const int N = 510;

int T, n, m;
char g[N][N];
int dist[N][N];
bool st[N][N];

void solve()
{
    memset(st, 0, sizeof st);
    memset(dist, 0x3f, sizeof dist);
    dist[0][0] = 0;
    deque<PII> deq;
    deq.push_back({0, 0});

    char state[] = {"\\/\\/"};
    int dx[] = {1, 1, -1, -1}, dy[] = {1, -1, -1, 1};
    int ix[] = {0, 0, -1, -1}, iy[] = {0, -1, -1, 0};

    while (deq.size())
    {
        PII t = deq.front();
        deq.pop_front();
        if (st[t.x][t.y]) continue;
        if (t.x == n && t.y == m) break;
        st[t.x][t.y] = true;

        for (int i = 0; i < 4; i ++ )
        {
            int a = t.x + dx[i], b = t.y + dy[i];
            if (a < 0 || a > n || b < 0 || b > m) continue;
            int w = g[t.x + ix[i]][t.y + iy[i]] != state[i];
            int d = w + dist[t.x][t.y];

            if (d < dist[a][b])
            {
                dist[a][b] = d;
                if (w) deq.push_back({a, b});
                else deq.push_front({a, b});
            }
        }
    }
    cout << dist[n][m] << endl;
}
int main()
{
    cin >> T;
    while (T -- )
    {
        cin >> n >> m;
        for (int i = 0; i < n; i ++ ) cin >> g[i];
        if ((n + m) & 1) puts("NO SOLUTION");
        else solve();
    }
    return 0;
}

工程课 Web-1.10. homework_10

编写一个完整的 HTML 页面。

页面中包含一行如下内容：

©<Web>版权所有

©<Web>版权所有

工程课 Web-1.9. homework_9

编写一个完整的 HTML 页面。

内容包括四个部分：

• header区：
  • 包含 <h3> 标题，内容为：我的收藏夹
• section区：
  • 包含 <h4> 标题，内容为：图片
  • 第一个 <figure>，包含一个 <img>，src 为 /images/logo.png，宽度为 100px，<figcaption> 的文本为：logo
  • 第二个 <figure>，包含一个 <img>，src 为 /images/mountain.jpg，宽度为 100px，<figcaption> 的文本为：山
• section区
  • 包含 <h4> 标题，内容为：古诗
  • 第一个 <article>，包含一个 <h5> 标题，内容为：春晓，之后包含一个段落，内容为：春眠不觉晓，处处闻啼鸟。夜来风雨声，花落知多少。
  • 第二个 <article>，包含一个 <h5> 标题，内容为：咏柳，之后包含一个段落，内容为：碧玉妆成一树高，万条垂下绿丝绦。不知细叶谁裁出，二月春风似剪刀。
• footer区
  • 包含一行文本：©2018-2022 Me 版权所有

<header>
    <h3>我的收藏夹</h3>
</header>

<section>
    <h4>图片</h4>
    <figure>
        <img src="/images/logo.png" width="100" alt="logo">
        <figcaption>logo</figcaption>
    </figure>
    <figure>
        <img src="/images/mountain.jpg" width="100" alt="山">
        <figcaption>山</figcaption>
    </figure>
</section>

<section>
    <h4>古诗</h4>
    <article>
        <h5>春晓</h5>
        <p>
            春眠不觉晓，处处闻啼鸟。夜来风雨声，花落知多少。
        </p>
    </article>
    <article>
        <h5>咏柳</h5>
        <p>
            碧玉妆成一树高，万条垂下绿丝绦。不知细叶谁裁出，二月春风似剪刀。
        </p>
    </article>
</section>

<footer>
    &copy;2018-2022 Me 版权所有
</footer>

工程课 Web-1.8. homework_8

编写一个完整的 HTML 页面。

页面中包含一个表格，要求：

表格的 标题 为：成绩单
表格的 内容 为：

<table>
    <caption>成绩单</caption>
    <thead>
        <tr>
            <th>姓名</th>
            <th>数学</th>
            <th>语文</th>
            <th>英语</th>
        </tr>
    </thead>
    <tr>
        <td>Alice</td>
        <td>100</td>
        <td>99</td>
        <td>98</td>
    </tr>
    <tr>
        <td>Bob</td>
        <td>99</td>
        <td>98</td>
        <td>97</td>
    </tr>
    <tr>
        <td>Tom</td>
        <td>98</td>
        <td>97</td>
        <td>96</td>
    </tr>
</table>

工程课 Web-1.7. homework_7

编写一个完整的 HTML 页面。

页面中包含一个有序列表：

• 列表第一项只包含一个文本，内容为：第一讲
• 列表第二项包含：
  • 一个文本，内容为：第二讲
  • 一个无序列表，包含3项，均为文本，内容分别为：第一小节、第二小节、第三小节。
• 列表第三项包含：
  • 一个文本，内容为：第三讲
  • 一个有序列表，包含3想，均为文本，内容分别为：第一小节、第二小节、第三小节。

<ol>
    <li>第一讲</li>
    <li>
        第二讲
        <ul>
            <li>第一小节</li>
            <li>第二小节</li>
            <li>第三小节</li>
        </ul>
    </li>
    <li>
        第三讲
        <ol>
            <li>第一小节</li>
            <li>第二小节</li>
            <li>第三小节</li>
        </ol>
    </li>
</ol>