Submission #1455818
Source Code Expand
#include<iostream> #include<vector> #include<string> #include<algorithm> #include<cstdio> #include<set> using namespace std; typedef long long ll; const ll INF = 1145141919; ll d[300][300]; ll n, m, k; string alp; string dfs(ll pos, string now, bool *used, bool isFirst){ if(now.size() >= k) return now; string ret; if(now.size() + 1 >= k) ret = now + alp[pos]; string emp; for(ll i = 0; i < n; ++i){ if(i != pos && !d[pos][i] && !used[i]){ used[pos] = 1; string add = dfs(i, now + alp[pos], used, 0); used[pos] = 0; if(add.size() >= k && (ret.empty() || ret > add)) ret = add; if(isFirst){ add = dfs(i, now, used, 0); if(add.size() >= k && (ret.empty() || ret > add)) ret = add; } } } return (ret.empty() ? emp : ret); } int main(){ cin >> n >> m >> k; for(ll i = 0; i < n; ++i){ for(ll j = 0; j < n; ++j){ d[i][j] = INF; } d[i][i] = 0; } for(ll i = 0; i < n; ++i){ char s; cin >> s; alp += s; } for(ll i = 0; i < m; ++i){ ll a, b; cin >> a >> b; --a; --b; d[a][b] = 0; } for(ll i = 0; i < n; ++i) for(ll j = 0; j < n; ++j) for(ll l = 0; l < n; ++l) d[j][l] = min(d[j][l], d[j][i] + d[i][l]); string ans; for(ll i = 0; i < n; ++i){ bool used[n] = {0}; string now; string add = dfs(i, now, used, 1); if(add.size() >= k && (ans.empty() || ans > add)) ans = add; } cout << (ans.size() ? ans : "-1") << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - 有向グラフ |
User | kcvlex |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1467 Byte |
Status | TLE |
Exec Time | 2103 ms |
Memory | 1024 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 100 | ||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask0_sample_04.txt |
All | subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask0_sample_04.txt, subtask1_manual01.txt, subtask1_manual02.txt, subtask1_manual03.txt, subtask1_manual04.txt, subtask1_manual05.txt, subtask1_manual06.txt, subtask1_manual07.txt, subtask1_manual08.txt, subtask1_random01.txt, subtask1_random02.txt, subtask1_random03.txt, subtask1_random04.txt, subtask1_random05.txt, subtask1_special01.txt, subtask1_special02.txt, subtask1_special03.txt, subtask1_special04.txt, subtask1_special05.txt, subtask1_special06.txt, subtask1_special07.txt, subtask1_special08.txt, subtask1_special09.txt, subtask1_special10.txt, subtask1_special11.txt, subtask1_special12.txt, subtask1_special13.txt, subtask1_special14.txt, subtask1_special15.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask0_sample_01.txt | AC | 1 ms | 256 KB |
subtask0_sample_02.txt | AC | 1 ms | 256 KB |
subtask0_sample_03.txt | AC | 1 ms | 256 KB |
subtask0_sample_04.txt | AC | 1 ms | 256 KB |
subtask1_manual01.txt | AC | 1 ms | 256 KB |
subtask1_manual02.txt | AC | 1 ms | 256 KB |
subtask1_manual03.txt | AC | 1 ms | 256 KB |
subtask1_manual04.txt | AC | 1 ms | 256 KB |
subtask1_manual05.txt | AC | 1 ms | 256 KB |
subtask1_manual06.txt | AC | 1 ms | 256 KB |
subtask1_manual07.txt | AC | 1 ms | 256 KB |
subtask1_manual08.txt | AC | 1 ms | 256 KB |
subtask1_random01.txt | TLE | 2103 ms | 1024 KB |
subtask1_random02.txt | TLE | 2103 ms | 896 KB |
subtask1_random03.txt | TLE | 2103 ms | 1024 KB |
subtask1_random04.txt | TLE | 2103 ms | 1024 KB |
subtask1_random05.txt | AC | 1492 ms | 896 KB |
subtask1_special01.txt | TLE | 2103 ms | 1024 KB |
subtask1_special02.txt | TLE | 2103 ms | 896 KB |
subtask1_special03.txt | TLE | 2103 ms | 1024 KB |
subtask1_special04.txt | TLE | 2103 ms | 1024 KB |
subtask1_special05.txt | TLE | 2103 ms | 1024 KB |
subtask1_special06.txt | TLE | 2103 ms | 1024 KB |
subtask1_special07.txt | TLE | 2103 ms | 1024 KB |
subtask1_special08.txt | TLE | 2103 ms | 1024 KB |
subtask1_special09.txt | TLE | 2103 ms | 1024 KB |
subtask1_special10.txt | TLE | 2103 ms | 1024 KB |
subtask1_special11.txt | TLE | 2103 ms | 1024 KB |
subtask1_special12.txt | TLE | 2103 ms | 1024 KB |
subtask1_special13.txt | TLE | 2103 ms | 1024 KB |
subtask1_special14.txt | AC | 32 ms | 896 KB |
subtask1_special15.txt | TLE | 2103 ms | 1024 KB |