A算法*
保证一定有解，不然算法不如dfs；无解会很慢，只能先写写去试试
179. 八数码
在一个 3×3的网格中，1∼8这 8个数字和一个 x 恰好不重不漏地分布在这 3×3
的网格中。
例如：
1 2 3
x 4 6
7 5 8
在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。
我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：
1 2 3
4 5 6
7 8 x
例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。
交换过程如下：
1 2 3 1 2 3 1 2 3 1 2 3
x 4 6 4 x 6 4 5 6 4 5 6
7 5 8 7 5 8 7 x 8 7 8 x
把 x 与上下左右方向数字交换的行动记录为 u、d、l、r。
现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。
输入格式
输入占一行，将 3×3的初始网格描绘出来。
例如，如果初始网格如下所示：
1 2 3
x 4 6
7 5 8
则输入为：1 2 3 x 4 6 7 5 8
输出格式
输出占一行，包含一个字符串，表示得到正确排列的完整行动记录。
如果答案不唯一，输出任意一种合法方案即可。
如果不存在解决方案，则输出 unsolvable。
输入样例：
2 3 4 1 5 x 7 6 8
输出样例
ullddrurdllurdruldr
解题思路
逆序对数必须是偶数才能有解，每次一个移动都会改变两个位置之间的逆序关系，因此必须是偶数
估价函数：当前状态中每个数和他目标位置的曼哈顿距离
#include<iostream>
#include<cstring>
#include<algorithm>
#include<unordered_map>
#include<queue>
#define x first
#define y second
using namespace std;
typedef pair<int,string> pis;
int f(string state){
int res=0;
for(int i=0;i<state.size();i++){
if(state[i]!='x'){//看清楚啊，不等于号！！！！！！！！！！
int t=state[i]-'1';
res+=abs(i/3-t/3)+abs(i%3-t%3);
}
}
return res;
}
string bfs(string start){
string end="12345678x";
unordered_map<string,int> dist;
char op[]="urdl";
unordered_map<string ,pair<char,string>> prev;//记录操作记录
priority_queue<pis,vector<pis>,greater<pis>> heap;
dist[start]=0;
heap.push({f(start),start});
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
while(heap.size()){
auto t=heap.top();
heap.pop();
string state=t.y;
if(state == end) break;
int x,y;
for(int i=0;i<9;i++){//寻找字符x的位置
if(state[i]=='x'){
x=i/3,y=i%3;
break;
}
}
string source = state;
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;
state=source;
swap(state[x*3+y],state[a*3+b]);
if(dist.count(state)==0||dist[state]>dist[source]+1){
dist[state]=dist[source]+1;
prev[state]={op[i],source};
heap.push({dist[state]+f(state),state});
}
}
}
string res;
while(end!=start)
{
res+=prev[end].x;
end=prev[end].y;
}
reverse(res.begin(),res.end());
return res;
}
int main(){
string start,seq;
char c;
while(cin>>c){
start+=c;
if(c!='x') seq+=c;
}
int cnt=0 ;
for(int i=0;i<8;i++){
for(int j=i;j<8;j++){
if(seq[i]>seq[j])
cnt++;
}
}
if(cnt&1) puts("unsolvable");
else cout<<bfs(start)<<endl;
return 0;
}
178. 第K短路
给定一张 N个点（编号 1,2…N），M条边的有向图，求从起点 S到终点 T的第 K短路的长度，路径允许重复经过点或边。
注意： 每条最短路中至少要包含一条边。
输入格式
第一行包含两个整数 N和 M。
接下来 M 行，每行包含三个整数 A,B和 L，表示点 A 与点 B 之间存在有向边，且边长为 L。
最后一行包含三个整数 S,T和 K，分别表示起点 S，终点 T和第 K短路。
输出格式
输出占一行，包含一个整数，表示第 K短路的长度，如果第 K短路不存在，则输出 −1。
数据范围
1≤S,T≤N≤1000,
0≤M≤104,
1≤K≤1000,
1≤L≤100
输入样例：
2 2
1 2 5
2 1 4
1 2 2
输出样例：
14
#include <cstring>
#include <iostream>
#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 = 200010;
int n, m, S, T, K;
int h[N], rh[N], e[M], w[M], ne[M], idx;
int dist[N], cnt[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()
{
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, T});
memset(dist, 0x3f, sizeof dist);
dist[T] = 0;
while (heap.size())
{
auto t = heap.top();
heap.pop();
int ver = t.y;
if (st[ver]) continue;
st[ver] = true;
for (int i = rh[ver]; ~i; 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 astar()
{
priority_queue<PIII, vector<PIII>, greater<PIII>> heap;
heap.push({dist[S], {0, S}});
while (heap.size())
{
auto t = heap.top();
heap.pop();
int ver = t.y.y, distance = t.y.x;
cnt[ver] ++ ;
if (cnt[T] == K) return distance;
for (int i = h[ver]; ~i; i = ne[i])
{
int j = e[i];
if (cnt[j] < K)//以j为终点的如果超过了k次数，那就没必要再进队了，反正不符合题意，这个剪枝很重要
heap.push({distance + w[i] + dist[j], {distance + w[i], j}});
}
}
return -1;
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
memset(rh, -1, sizeof rh);
for (int i = 0; i < m; i ++ )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(h, a, b, c);
add(rh, b, a, c);
}
scanf("%d%d%d", &S, &T, &K);
if (S == T) K ++ ;
dijkstra();
printf("%d\n", astar());
return 0;
}