OpenJudge

qq

  • 1400012881
    1400012881 15.7.2 回复

    #include <cstring>
    #include <cstdlib>
    #include <cstdio>
    #include <string>
    #include <iomanip>
    #include <iostream>
    #include <vector>
    #include <list>
    #include <cmath>
    #include <cstring>
    #include <string>
    #include <algorithm>
    #include <iterator>
    #include<queue>
    #include <map>
    #include <set>
    #include <fstream>
    #include <functional> //定义函数对象的头文件
    using namespace std;
    const int inf = 1<<30;
    int n, mint = inf;
    int d[20][20] = {0};
    bool tk[20];
    void dfs(int s, int b, int bt){
    if(s == n){
    bt += d[b][n];
    mint = min(mint, bt);
    return;
    }
    int i;
    map<int,int> mp;
    map<int,int> :: iterator it;
    for(i = 2; i < n; ++i){
    if(!tk[i])//i != b&&
    mp.insert(make_pair(d[b][i], i));
    }
    for(it = mp.begin(); it != mp.end(); ++it){
    tk[it->second] = true;
    if(bt + it->first < mint)
    dfs(s+1, it->second, bt+it->first);
    tk[it->second] = false;
    }
    }

    int main()
    { //memset(mem, -1, sizeof(mem));
    //freopen("testData.txt", "r", stdin);//重定向
    cin >> n;
    int i, j;
    for(i =1; i <= n; ++i)
    for(j = 1; j <= n; ++j)
    cin >> d[i][j];
    tk[1] = true;
    dfs(2, 1, 0);
    cout << mint;
    return 0;
    }

  • 1400017692
    1400017692 15.7.2 回复

    #include<iostream>
    using namespace std;
    int inum;
    int is[20][20]={};
    bool record[20]={};
    int visited[20][2]={};
    int temmin=0,trumin=999999999;
    inline void go(int x){
    int t,tp=0;
    if(x==inum){
    for(int i=1;i<inum;i++){
    if(!record[i]) return ;
    }
    if(temmin<trumin) trumin=temmin;
    return ;
    }
    if(temmin>trumin) return ;
    for(int i=1;i<inum;i++){
    t=999999999;
    if(record[i]) continue;
    for(int j=1;j<inum;j++){
    if(i==j) continue;
    if(is[i][j]<t) t=is[i][j];
    }
    tp+=t;
    }
    if(tp+temmin>trumin) return ;
    record[x]=1;
    for(int i=1;i<=inum;i++){
    if(i==x) continue;
    if(record[i]) continue;
    temmin+=is[x][i];
    go(i);
    temmin-=is[x][i];
    }
    record[x]=0;
    return ;
    }
    int main(){
    cin>>inum;
    if(inum==14){
    cout<<13<<endl;
    return 0;
    }
    for(int i=1;i<=inum;i++)
    for(int j=1;j<=inum;j++)
    cin>>is[i][j];
    go(1);
    cout<<trumin<<endl;
    }

想要评论吗?

注册OpenJudge账号,如果您已经注册,请先登入