如题。

#include<bits/stdc++.h>

using namespace std;

const int N=405;

int n,m;
vector<pair<int,char>> vec[N],fvec[N];

int f[N][N],s[N];
bitset<N> to[N],uvis[N];

pair<int,int> lst[N][N];
char mp[N][N];

queue<pair<int,int>> que;
int main() {
	cin >> n >> m;
	
	int u,v;char w;
	for(int i=1;i<=m;++i) {
		cin >> u >> v >> w;
		vec[u].push_back({v,w});
		fvec[v].push_back({u,w});
		mp[u][v]=w;
	}
	
	for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) if(i!=j) uvis[i][j]=1;
	for(int u=1;u<=n;++u) {
		for(auto& [v,w]:vec[u]) {
			uvis[u][v]=0,to[u][v]=1,f[u][v]=1;
			que.push({u,v});
		}
	}
	
	for(int u=1;u<=n;++u) {
		for(auto& [v,w]:vec[u]) {
			for(auto& [k,w2]:vec[v]) {
				if(w!=w2) continue;
				uvis[u][k]=0,f[u][k]=2;
				que.push({u,k});
			}
		}
	}
	
	bitset<N> B;
	while(!que.empty()) {
		auto& [u,v]=que.front();
		que.pop();
		
		for(auto& [q,w]:fvec[u]) {
			B=uvis[q]&to[v];
			for(int p=B._Find_first();p!=B.size();p=B._Find_next(p)) {
				if(w!=mp[v][p]) continue;
				uvis[q][p]=0,f[q][p]=f[u][v]+2;
				lst[q][p]={u,v};
				que.push({q,p});
			}
		}
	}
	
	int d;string s1;char c;
	cin >> d;
	cin >> s[1];
	for(int i=2;i<=d;++i) {
		cin >> s[i];
		if(!f[s[i-1]][s[i]]) {
			cout << -1 << endl;
			continue;
		}
		cout << f[s[i-1]][s[i]] << ' ';
		int u=s[i-1],v=s[i],nu,nv;s1="",c=' ';
		while(u&&v) {
			nu=lst[u][v].first,nv=lst[u][v].second;
			if(nu) s1+=mp[u][nu];
			else if(u!=v) c=mp[u][v];
			u=nu,v=nv;
		}
		cout << s1;
		if(c!=' ') cout << c;
		reverse(s1.begin(),s1.end());
		cout << s1 << endl;
	}
}