75 - F.與冰精靈健行 - 竹園論壇

[C++] 純文本查看 復制代碼
#include<iostream>

#include<cstdlib> 

#include<algorithm> 

#include<climits> 

#include<ctime> 

using namespace std;

int n,m;

int g[110][110];

int road[110];

int solve()

{

    int ans=INT_MAX;

    for(int no=0;no<1000000;no++)

    {

        int cg1=rand()%n,cg2=rand()%n;

        //cout<<cg1<<" "<<cg2<<endl;

        swap(road[cg1],road[cg2]);

        int newans=0;

        for(int i=1;i<n;i++)

            newans+=g[road[i-1]][road];

        if(newans<ans)

            ans=newans;

        else

            swap(road[cg1],road[cg2]);

    }

    return ans;

}

int main()

{

    srand(time(NULL));

    cin>>n>>m;

    for(int i=0;i<n;i++)

        for(int j=0;j<n;j++)

            g[j]=1e8;

    for(int i=0;i<m;i++)

    {

        int a,b,c;

        cin>>a>>b>>c;

        a--; b--;

        g[a]=g[a]=min(g[a],c);

    }

    for(int i=0;i<n;i++)

        g=0;

    for(int k=0;k<n;k++)

        for(int i=0;i<n;i++)

            for(int j=0;j<n;j++)

                g[j]=min(g[j],g[k]+g[k][j]);

    

    int ans=INT_MAX;

    for(int no1=0;no1<100;no1++)

    {

        bool used[110]={0};

        for(int i=0;i<n;i++)

        {

            do{

                road=rand()%n;

            }while(used[road]);

            used[road]=1;

        }

        ans=min(ans,solve());

        cout<<ans<<endl;

    }

    cout<<ans<<endl;

}