#include  <iostream>
#include <cstring>

using namespace std;
const int N = 20;
int n;
bool st[N];
int group[N][N],s[N],ans = N;
int gcd(int a,int b)
{
    return b?gcd(b,a % b):a;
}
bool check(int group[],int gc,int pos)
{
    for(int i = 0;i<gc;i++)
    if(gcd(s[group[i]],s[pos]) != 1) return false;
    return true;
}
void dfs(int g,int gc,int tc,int start)//g代表当前用到第几组，gc代表当前枚举到第g组第几个位置，tc代表当前枚举当第几个数
{
    if(g >= ans) return ;
    if(tc == n)
    {
        ans = g;
        return;
    }
    bool  flag = true;
    for(int i = start;i<n;i++)
    if(!st[i] && check(group[g],gc,i))
    {
        st[i] = true;
        group[g][gc] = i;
        dfs(g,gc+1,tc+1,i + 1);
        st[i] = false;
        flag = false;
        if(gc == 0) break;
    }
    if(flag) dfs(g+1,0,tc,0);
}
int main(void)
{
    cin>>n;
    for(int i = 0;i<n;i++) cin>>s[i];
    dfs(1,0,0,0);
    cout<<ans<<endl;
    return 0;
}

#include <iostream>
#include <unordered_map>
#include <cstdio>

using namespace std;
const int N = 20  + 10;
int n;
unordered_map<string,int> vis;
string ss[N];
pair<string,bool> change(string str,string s)//第二个参数判断是否可以接在后面
{
    int n = str.size(), m = s.size();
    string ans = "";
    bool flag = false;
    if(str.size() == 1 && str[0] ==  s[0])//当为首字母时特判一下
    {
        ans = s;
        flag = true;
    }
    else
    {
        for(int  i =  1;i< min(n,m);i++)//在有许多重合部分时，枚举最短的重合部分达到最长
        {
            string temp = str.substr(n-i),temp2 =  s.substr(0,i);
            if(temp == temp2) 
            {
                ans = str + s.substr(i);
                flag = true;
                break;
            }
        }        
    }

    return  make_pair(ans,flag);
}
int dfs(string start)
{
    int len = 0;
    len = max(len,(int)start.size());
    for(int i = 0;i<n;i++)
    if(vis[ss[i]] < 2)
    {
        vis[ss[i]] ++;
        pair<string,bool> p = change(start,ss[i]);
        if(p.second) len = max(len,dfs(p.first));        
        vis[ss[i]] --;
    }
    return  len;
}
int main(void)
{
    scanf("%d",&n);

    for(int i = 0;i<n;i++) cin>>ss[i];
    string start;
    cin>>start;
    cout<<dfs(start)<<endl;
    return 0;
}

#include <iostream>
#include <cstring>
using namespace  std;

const int N = 20;

bool st[N][N];
int n ,m;

int dx[] = {-2,-2,-1,1,2,2,1,-1},dy[] = {-1,1,2,2,1,-1,-2,-2};
int dfs(int sx,int sy,int step)
{
    int cnt= 0;
    st[sx][sy] = true;
    if(step == n * m)
    {
        cnt ++;
        return cnt;
    }
    for(int i = 0;i<8;i++)
    {
        int x = sx + dx[i],y = sy + dy[i];
        if(x < 0 || x >= n || y < 0 || y >= m) continue;
        if(st[x][y]) continue;
        cnt += dfs(x,y,step + 1);
        st[x][y] =false;
    }
    return cnt;
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        int x,y;
        cin>>n>>m>>x>>y;
        memset(st,false,sizeof st);
        cout<<dfs(x,y,1)<<endl;
    }
    return 0;
}

#include <iostream>
#include <cstring>
using namespace std;

const int N = 30;
char g[N][N];
bool st[N][N];
int n,m,cnt;
int  dx[]  = {-1,0,1,0},dy[] = {0,1,0,-1};
void dfs(int sx,int sy)
{
    cnt++;
    st[sx][sy] = true;

    for(int i = 0;i<4;i++)
    {
        int x = sx + dx[i],y = sy + dy[i];
        if(x < 0 || x >= n || y < 0 || y >= m) continue;
        if(g[x][y] != '.') continue;
        if(st[x][y])    continue;
        dfs(x,y);
    }
}
int  main(void)
{
    while(cin>>m>>n,n && m)
    {
        cnt = 0;
        memset(st,false,sizeof st);
        int sx,sy;
        for(int i = 0;i<n;i++) scanf("%s",g[i]);
        for(int i = 0;i<n;i++)
            for(int j = 0;j<m;j++) if(g[i][j] == '@') sx = i,sy = j;
        dfs(sx,sy);
        cout<<cnt<<endl;
    }
    return 0;
}

#include <cstring>
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 110;
char g[N][N];
int n,ex,ey;
bool st[N][N];
int dx[] = {-1,0,1,0},dy[] =  {0,1,0,-1};
bool dfs(int sx,int sy)//两种到达终点的方式,本身就到达,或者通过其他方式到达
{

    st[sx][sy] = true;
    if(g[sx][sy] != '.')  return false;
    if(sx == ex && sy == ey) return true;
    for(int i = 0;i<4;i++)
    {
        int x = sx + dx[i],y = sy + dy[i];
        if(x < 0 || x >= n || y < 0 || y >= n) continue;
        if(st[x][y]) continue;
        st[x][y] = true;
        if(dfs(x,y)) return true;//如果只是dfs(x,y)则少了一条可以到达的点
        //为什么不加st[x][y] = false,因为通过(x,y)不能到达的点不需要状态还原
    }
    return false;
}
int main(void)
{
    int k;
    scanf("%d",&k);
    while(k--)
    {
        scanf("%d",&n);
        memset(st,false,sizeof st);
        for(int i =  0;i<n;i++)  scanf("%s",g[i]);
        int sx,sy;
        scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
        if(dfs(sx,sy)) puts("YES");
        else puts("NO");
    }
    return 0;
}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int N = 1e3 + 10,C = 110,M = 2e4 + 10;
int h[N],e[M],ne[M],w[M],idx = 1,n,m,price[N];
void add(int a,int b,int c)
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx ++;
}
struct po{
    int d,n,c;
    bool operator < (const po &t) const{
        return d > t.d;
    }
    po (int d,int n,int c)
    {
        this->d = d;this->n = n;this->c = c;
    }
};
bool st[N][C];
int dis[N][C];
int dijkstra(int s,int end,int c)
{
    memset(dis,0x3f,sizeof(dis));
    memset(st,false,sizeof(st));
    priority_queue<po> heap;
    heap.push(po(0,s,0));
    dis[s][0] = 0;

    while(heap.size())
    {
        po s = heap.top();
        heap.pop();

        int d = s.d,now = s.n,sav = s.c;
        if(st[now][sav]) continue;
        st[now][sav] = true;
        if(now == end) return dis[now][0];

        if(sav < c)
        {
            if(dis[now][sav + 1] > dis[now][sav] + price[now])
            {
                dis[now][sav + 1] = dis[now][sav] + price[now];
                heap.push(po(dis[now][sav + 1] ,now,sav+1));
            }
        }
        for(int i = h[now];~i;i = ne[i])
        {
            int b = e[i];
            if(sav >= w[i])
            {
                if(dis[b][sav - w[i]] > dis[now][sav])
                {
                    dis[b][sav-w[i]] = dis[now][sav];
                    heap.push(po(dis[b][sav-w[i]],b,sav-w[i]));
                }
            }
        }
    }
    return  -1;
}
int main(void)
{
    memset(h,-1,sizeof(h));
    scanf("%d%d",&n,&m);
    for(int i = 0;i<n;i++) scanf("%d",&price[i]);
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
    }
    int q;
    scanf("%d",&q);
    while(q--)
    {
        int c,s,e;
        scanf("%d%d%d",&c,&s,&e);
        int t = dijkstra(s,e,c);
        if(t == -1) puts("impossible");
        else printf("%d\n",t);
    }
    return 0;
}

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#define x first
#define y second
using namespace std;
const int N = 1e3 + 10,M = 2e5 + 10;
int h[N],rh[N],ne[M],e[M],w[M],idx;
bool st[N];
int dist[N],S,T,K;
typedef pair<int,int> pll;
int cnt[N];
void add(int t[],int a,int b,int c)
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = t[a];
    t[a] = idx ++;
}
void dijkstra()
{
    memset(dist,0x3f3f3f3f,sizeof dist);
    priority_queue<pll,vector<pll>,greater<pll> > heap; 
    heap.push(make_pair(0,T));
    dist[T] = 0;

    while(heap.size())
    {
        pll s = heap.top();
        heap.pop();

        int ver = s.y;
        if(st[ver]) continue;
        st[ver] = true;

        for(int i = rh[ver];~i;i = ne[i])
        {
            int b = e[i];
            if(dist[b] > dist[ver] + w[i])
            {
                dist[b] = dist[ver] + w[i];
                heap.push(make_pair(dist[b],b));
            }
        }
    }
}

int astar()
{

    pll p = make_pair(dist[S],S);
    priority_queue<pll,vector<pll>,greater<pll>> heap;
    heap.push(p);
    if(dist[0] == dist[S]) return -1;
    while(heap.size())
    {
        pll s = heap.top();
        heap.pop();
        int ver = s.y,distance = s.x - dist[ver];
        cnt[ver] ++;
        if(cnt[T] == K) return distance;
        for(int i = h[ver];~i;i = ne[i])
        {
            int b = e[i];
            if(cnt[b] < K) heap.push(make_pair(distance + w[i] + dist[b],b));
        }
    }
    return -1;
}
int main(void)
{
    int n, m;
    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;
}

代码如下

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#define x first
#define y second
using namespace std;
const int N = 1e3 + 10,M = 2e5 + 10;
int h[N],rh[N],ne[N],e[N],w[N],idx;
bool st[N];
int dist[N],S,T,K;
typedef pair<int,int> pll;
int cnt[N];
void add(int t[],int a,int b,int c)
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = t[a];
    t[a] = idx ++;
}
void dijkstra()
{
    memset(dist,0x3f3f3f3f,sizeof dist);
    priority_queue<pll,vector<pll>,greater<pll> > heap; 
    heap.push(make_pair(0,T));
    dist[T] = 0;

    while(heap.size())
    {
        pll s = heap.top();
        heap.pop();

        int ver = s.y;
        if(st[ver]) continue;
        st[ver] = true;

        for(int i = rh[ver];~i;i = ne[i])
        {
            int b = e[i];
            if(dist[b] > dist[ver] + w[i])
            {
                dist[b] = dist[ver] + w[i];
                heap.push(make_pair(dist[b],b));
            }
        }
    }
}

int astar()
{

    pll p = make_pair(dist[S],S);
    priority_queue<pll,vector<pll>,greater<pll>> heap;
    heap.push(p);
    if(dist[0] == dist[S]) return -1;
    while(heap.size())
    {
        pll s = heap.top();
        heap.pop();
        int ver = s.y,distance = s.x - dist[ver];
        cnt[ver] ++;
        if(cnt[T] == K) return distance;
        for(int i = h[ver];~i;i = ne[i])
        {
            int b = e[i];
            if(cnt[b] < K) heap.push(make_pair(distance + w[i] + dist[b],b));
        }
    }
    return -1;
}
int main(void)
{
    int n, m;
    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;
}

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <queue>

using namespace std;

const int N = 6;

string a[N], b[N];
int n;

int extend(queue<string>& q, unordered_map<string, int>& da, unordered_map<string, int> &db, string a[], string b[])
{
    auto str = q.front();
    q.pop();

    for(int i = 0; i < str.size(); i ++)
        for(int j = 0; j < n; j ++)
            if(str.substr(i, a[j].size()) == a[j])
            {
                string temp = str.substr(0, i) + b[j] + str.substr(i + a[j].size());
                if(db.count(temp))return da[str] + 1 + db[temp];
                if(da.count(temp))continue;
                da[temp] = da[str] + 1;
                q.push(temp);
            }
    return -1;
}

int bfs(string A, string B)
{
    queue<string> qa, qb;
    unordered_map<string, int> da, db;
    qa.push(A), qb.push(B);
    da[A] = 0, db[B] = 0;
    while(qa.size() && qb.size())
    {
        int t;
        if(qa.size() < qb.size()) t = extend(qa, da, db, a, b);
        else t = extend(qb, db, da, b, a);
        if(t != -1)return t;
    }
    return 11;
}

int main()
{
    string A, B;
    cin >> A >> B;

    while(cin >> a[n] >> b[n])n ++;

    int step = bfs(A, B);

    if(step > 10)puts("NO ANSWER!");
    else cout << step << endl;
    return 0;
}

#include <iostream>
#include <cstdio>
#include <unordered_map>
#include <queue>
#include <algorithm>
#define x first
#define y second
using namespace std;
string start,en;
typedef pair<string,int> psl;

int f(string s)
{
    int res =  0;
    for(int i = 0;i<9;i++)
    if(s[i] != 'x')
    {
        int t = s[i] - '1';
        res += abs(i / 3 - t / 3 ) + abs(i % 3 - t % 3);
    }
    return res;
}
struct cmp
{
    bool operator() (psl a,psl b)
    {
        return a.y > b.y;
    }
};
int bfs(string start)
{
    en = "12345678x";
    int dx[] = {-1,1,0,0},dy[] = {0,0,-1,1};
    char op[] = "udlr";
    unordered_map<string,int> dis;
    unordered_map<string,pair<string,char>> prev;
    priority_queue<psl,vector<psl>,cmp> heap;
    dis[start] = 0;
    psl p = make_pair(start,f(start));
    heap.push(p);

    while(heap.size())
    {
        psl s = heap.top();
        heap.pop();

        string str = s.x;
        int distance = dis[str];
        if(str == en) break;

        int sx,sy;
        for(int i = 0;i<9;i++)
        if(str[i] == 'x') sx = i / 3,sy = i % 3;

        for(int i = 0;i<4;i++)
        {
            int nx = sx + dx[i],ny = sy + dy[i];
            if(nx < 0 || nx >= 3 || ny < 0 || ny >= 3) continue;
            string nstr = str;
            swap(nstr[nx * 3 + ny],nstr[sx * 3 + sy]);
            if(dis.count(nstr) && dis[nstr] <= distance + 1)  continue;
            dis[nstr] = distance + 1;
            pair<string,char> tmp = make_pair(str,op[i]);
            prev[nstr] = tmp;
            psl ps = make_pair(nstr,f(nstr) + dis[nstr]);
            heap.push(ps);
        }
    }
    string ans;

    while(en != start)
    {
        ans += prev[en].y;
        en = prev[en].x;
    }
    reverse(ans.begin(),ans.end());
    cout<<ans<<endl;
}
int main(void)
{
    string tmp,seq;
    for(int i = 0;i<9;i++)
    {
        cin>>tmp;
        start += tmp;
        if(tmp != "x") seq += tmp;
    }
    int cnt = 0;
    for(int i = 0;i<seq.size();i++)
        for(int j = i + 1;j<seq.size();j++)
            if(seq[i] > seq[j]) cnt ++;

    if(cnt & 1) cout<<"unsolvable"<<endl;
    else bfs(start);
    return 0;
}