哪位大佬帮我看看这个代码为什么有两个点TLE
查看原帖
哪位大佬帮我看看这个代码为什么有两个点TLE
505959
YangJinxi_7_22楼主2022/2/9 23:30
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
const int N = 1005;
int n;
string s[N];
bool vis[N*N] , flag = 0;
int head[N] , tot = 0;
struct edge{
    int to , nxt;
}e[N*N*2];

bool cmp( string a , string b ){
    for( int i = 0 ; i < min( a.size( )  , b.size( ) ) ; i++ ){
        if( a[i] < b[i] ) return 1;
        else if( b[i] < a[i] ) return 0;
    }
    return a.size( ) < b.size( );
}

void add( int u , int v ){
    e[++tot].to = v;
    e[tot].nxt = head[u];
    head[u] = tot;
}

vector<int> ans;

void dfs( int u ){
    ans.push_back( u );
    vis[u] = 1;
    for( int i = head[u] ; i ; i = e[i].nxt ){
        int v = e[i].to;
        if( !vis[v] ) dfs( v );
    }
    if( ans.size( ) == n ) flag = 1;
    else vis[u] = 0 , ans.pop_back( );
}

int main( ) {
    cin >> n;
    for( int i = 1 ; i <= n ; i++ ){
        cin >> s[i];
    }
    sort( s + 1 , s + n + 1 , cmp );
    for( int i = 1 ; i <= n ; i++ ){
        for( int j = n ; j >= 1 ; j-- ){
            if( i == j ) continue;
            if( s[j][0] == s[i][s[i].size( )-1] ){
                add( i , j );
            }
        }
    }
    for( int i = 1 ; i <= n ; i++ ){
        ans.clear( );
        //memset( vis , 0 , sizeof( 0 ) );
        dfs( i );
        if( ans.size( ) == n ){
            break;
        }
    }
    if( !flag ){
        cout << "***" <<endl;
        return 0;
    }
    for( int i = 0 ; i < ans.size( )-1 ; i++ ){
        cout << s[ans[i]] << ".";
    }
    cout << s[ans[ans.size( )-1]] <<endl;
    return 0;
}


2022/2/9 23:30
加载中...