Submission #1483906

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <array>
#include <cassert>
#include <bitset>
using namespace std;
using LL = long long;

namespace scc_space
{
	void dfs(int v_, vector<bool>&used_, vector<int>G_[], vector<int>&vs_)
	{
		used_[v_] = true;
		for (int nxt : G_[v_])
		{
			if (!used_[nxt])dfs(nxt, used_, G_, vs_);
		}
		vs_.push_back(v_);
	}

	void rdfs(int v_, int k_, vector<bool>&used_, vector<vector<int>>&rG_, vector<int>&top)
	{
		used_[v_] = true;
		top[v_] = k_;
		for (int nxt : rG_[v_])
		{
			if (!used_[nxt])rdfs(nxt, k_, used_, rG_, top);
		}
	}
}

//頂点数n_のグラフG_の強連結成分分解をする
//topに強連結成分のトポロジカル順序が格納される
//(top[i]==top[j]のとき、iとjは強連結である。)
//戻り値:強連結成分の個数
int scc(vector<int>G_[], int n_, vector<int>&top)
{
	using namespace scc_space;
	top.resize(n_);
	vector<vector<int>>rG_(n_);
	for (int i = 0; i < n_; ++i)
	{
		for (int to : G_[i])
		{
			rG_[to].push_back(i);
		}
	}
	vector<bool>used(n_, false);
	vector<int>vs;
	for (int v = 0; v < n_; ++v)
	{
		if (!used[v])dfs(v, used, G_, vs);
	}
	fill(used.begin(), used.end(), false);
	int k = 0;
	for (int i = vs.size() - 1; i >= 0; --i)
	{
		if (!used[vs[i]])rdfs(vs[i], k++, used, rG_, top);
	}
	return k;
}


int n, m, k;
char c[300];
vector<int>graph[300];
vector<int>top;
map<int, string>vert;//頂点の文字集合
vector<int>press[300];//強連結をつぶした後のDAG
vector<int>prinv[300];//pressの逆グラフ
set<int>prraw[300];

//強連結iにいて、文字列の長さがjの時の文字列
string memo[345][345];
bool izryt[345][345];
const string& dp(int i, int j)
{
	if (izryt[i][j])return memo[i][j];
	string res(j, '~');
	if (prinv[i].empty())
	{
		res = vert[i];
		res.resize(j, '~');
	}
	else
	{
		for (int las : prinv[i])
		{
			for (int k = 0; k <= j; ++k)
			{
				string S = dp(las, j - k) + vert[i];
				if (S.size() < j)continue;
				S.resize(j);
				res = min(res, S);
			}
		}
	}
	memo[i][j] = res;
	izryt[i][j] = true;
	return memo[i][j];
}

int main(void)
{
	cin >> n >> m >> k;
	for (int i = 0; i < n; ++i)
		cin >> c[i];
	for (int i = 0; i < m; ++i)
	{
		int a, b;
		cin >> a >> b;
		--a; --b;
		graph[a].push_back(b);
	}
	scc(graph, n, top);
	for (int i = 0; i < n; ++i)
	{
		vert[top[i]].push_back(c[i]);
	}
	for (auto &p : vert)
	{
		sort(p.second.begin(), p.second.end());
	}
	for (int i = 0; i < n; ++i)
	{
		set<int>s;
		for (int to : graph[i])
		{
			s.insert(top[to]);
		}
		for (int to : s)
		{
			if (to == top[i])continue;
			prraw[top[i]].insert(to);
		}
	}
	for (int i = 0; i < n; ++i)
	{
		for (auto p : prraw[i])
		{
			press[i].push_back(p);
			prinv[p].push_back(i);
		}
	}
	string ans(k, '~');
	for (int i = 0; i < n; ++i)
	{
		string can = dp(i, k);
		ans = min(ans, can);
	}
	if (ans.find('~') != string::npos)
	{
		cout << "-1\n";
	}
	else
	{
		cout << ans << endl;
	}
	return 0;
}

Submission Info

Judge Result