题解 | #kotori和素因子#

/*
最短路径，这里使用用回溯的方法求解，
具体思路就是假设在经过某个节点的时候，
当前已走过的路径为path（即使用过的素因子集），
然后遍历当前节点下可选的素因子，深入搜索，
然后再回溯，当节点id等于n时，记录此时的总和，
与当前最小的总和进行比较更新，然后返回。
*/
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

vector<int> an;
int n,ans0=1e+6;
//判断是否是素数
bool isprime(int ai){ //ai>=2
    for(int i=2;i*i<=ai;++i){
        if(ai%i==0)return false;//非素数
    }
    return true;//素数
}
// 统计素因子
vector<int> find_way(int a){
    vector<int> chooses;
    for(int i=2;i*i<=a;++i){
        if(a%i==0)//是非1的因子
        {
            if(isprime(i))chooses.push_back(i);
            if(isprime(a/i)&&i!=(a/i))chooses.push_back(a/i);
        }
    }
    if(chooses.empty())chooses.push_back(a);//说明该数为素数
    return chooses;
}
//dfs
void dfs(int id, unordered_set<int>& path, int ans){
    //cout<<"id_now= "<<id<<endl;
    if(id==n){
        ans0 = min(ans,ans0);
        return;
    }
    vector<int> chooses = find_way(an[id]);
    if(chooses.empty())cout<<"id_now= "<<id<<endl;
    for(int choose:chooses){
        //cout<<choose<<endl;
        if(!path.count(choose)){
            path.insert(choose);
            dfs(id+1,path,ans+choose);
            path.erase(choose);//回溯
        }
    }
}
int main() {
    int ai,ans=0;
    cin>>n;
    for(int i=0;i<n;++i){
        cin>>ai;
        an.push_back(ai);
    }
    unordered_set<int> path;
    dfs(0,path,ans);
    if(ans0==1e+6)cout<<-1;
    else cout<<ans0;
    return 0;
}
// 64 位输出请用 printf("%lld")