求dalao优化 TLE……

#include<iostream>
#include<algorithm>
#include<cstring>
#define INF 1100000000
using namespace std;
int a[100005],b[100005],c,maxn,maxq,maxw,maxe,maxr,maxo,maxp,pan,max1,max2,ans;
int dis[20005][20005],bj[20005],pri1[20005],pri2[20005];
int main()
{
    
    std::ios::sync_with_stdio(false);
    memset(bj,1,sizeof(bj));
    memset(dis,INF,sizeof(dis));
    int n,m;
    cin>>n>>m;
    for(long long i=1;i<=n;++i)
    dis[i][i]=0;
    for(int i=1;i<=m;++i)
    {
        cin>>a[i]>>b[i]>>c;
        dis[a[i]][b[i]]=c;
        dis[b[i]][a[i]]=dis[a[i]][b[i]];
    }
    for(int k=1;k<=n;++k)
    {
        for(int i=1;i<=n;++i)
        {
            for(int j=1;j<=n;++j)
            {
                if(dis[i][k]+dis[k][j]<dis[i][j]&&i!=j&&i!=k&&k!=j)
                dis[i][j]=dis[i][k]+dis[k][j];
            }
        }
    }
    int n1=n,cr1,cr2,js1=1,js2=1;
    while(n1>0)
    {
        maxn=-1,maxq=-1,maxw=-1,maxe=-1,maxr=-1,maxo=-1,maxp=-1;
        for(int i=1;i<=n;++i)
        {
            for(int j=1;j<=n;++j)
            {
                if(dis[i][j]>maxn&&bj[i]!=0&&bj[j]!=0)
                {           
                    maxn=dis[i][j];
                    cr1=i;
                    cr2=j;
                }
            }   
        }                    
        if(n1==n)
        {
            pri1[js1]=cr1;
            pri2[js2]=cr2;
        }
        else
        {
            if(n1==1)
            {
                for(int j=1;j<=js1-1;++j)
                if(dis[pri1[j]][cr1]>maxo)
                maxo=dis[pri1[j]][cr1];
                for(int j=1;j<=js2-1;++j)
                if(dis[pri2[j]][cr1]>maxp)
                maxp=dis[pri2[j]][cr1];
                if(maxo>maxp)
                pri2[js2]=cr1;
                else
                pri1[js1]=cr1;
            }
            else
            {   
                for(int j=1;j<=js1-1;++j)
                {
                    if(dis[pri1[j]][cr1]>maxq)
                    maxq=dis[pri1[j]][cr1];
                    if(dis[pri1[j]][cr2]>maxw)
                    maxw=dis[pri1[j]][cr2];
                }
                for(int j=1;j<=js2-1;++j)
                {
                    if(dis[pri2[j]][cr1]>maxe)
                    maxe=dis[pri2[j]][cr1];
                    if(dis[pri2[j]][cr2]>maxr)
                    maxr=dis[pri2[j]][cr2];
                }
                pan=max(max(maxq,maxw),max(maxe,maxr));
                if(pan==maxq||pan==maxr)
                {
                    pri1[js1]=cr2;
                    pri2[js2]=cr1;
                }
                if(pan==maxw||pan==maxe)
                {
                    pri1[js1]=cr2;
                    pri2[js2]=cr1;
                }
            }
        }
        bj[cr1]=0;
        bj[cr2]=0;
        js1++;
        js2++;
        n1-=2;
    }  
    for(int i=1;i<=js1-1;++i)
    {
        for(int j=1;j<=js1-1;++j)
        {
            if(dis[pri1[i]][pri1[j]]>max1)
            max1=dis[pri1[i]][pri1[j]];
        }
    }
    for(int i=1;i<=js2-1;++i)
    {
        for(int j=1;j<=js2-1;++j)
        {
            if(dis[pri2[i]][pri2[j]]>max2)
            max2=dis[pri2[i]][pri2[j]];
        }
    }                       
    ans=max(max1,max2);
    cout<<ans;
    return 0;
}

0 条评论

目前还没有评论...

信息

ID
1776
难度
6
分类
图结构 | 二分图 点击显示
标签
递交数
3543
已通过
1015
通过率
29%
被复制
11
上传者