$\href{https://colopen-blog.com}{Colopen's \ blog}$

35.5万

Zcr

Chiullian
anbo
mhmh
acwing_1793
yume

sanowip
_wolf

1024M
moodles

Jagger_2
yyxxx

femirins

Laurus_1

#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;
}


#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;
}


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;
}
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>版权所有

&copy;&lt;Web&gt;版权所有


• 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>

<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>


Alice 100 99 98
Bob 99 98 97
Tom 98 97 96
<table>
<caption>成绩单</caption>
<tr>
<th>姓名</th>
<th>数学</th>
<th>语文</th>
<th>英语</th>
</tr>
<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>


• 列表第一项只包含一个文本，内容为：第一讲
• 列表第二项包含：
• 一个文本，内容为：第二讲
• 一个无序列表，包含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>