解题思路：

本题要求判断哪些公司能提供从起点到终点的完整路径。每条路径上的所有连接必须属于同一公司。由于节点数最多为$200$，直接遍历所有路径显然不高效。因此，采用改进的$Floyd$算法来处理所有中间节点情况，动态维护各公司可达性。

位压缩存储：

每个公司对应一个二进制位，$d[i][j]$的每一位表示$i$到$j$是否存在某公司提供的完整路径。

Floyd变种：

通过中间节点k扩展路径时，只有当$i→k$和$k→j$的路径属于同一公司时，$i→j$的路径才对该公司有效。使用位运算中的与操作求交集，或操作合并结果。

动态规划状态转移：

$d[k][i][j]$表示中间节点不超过$k$时的公司集合，通过逐步加入中间节点更新所有路径的可能公司。

C++实现

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cstdio>
#include <queue>
using namespace std;
typedef pair<int,int> ii;
typedef long long ll;
const int N=2e2+20;
const ll inf=1e9;
ll d[N][N];// d(k)[a][b] 能提供a->b连接&&在中间节点序号不大于k时的公司的集合
//company集合用二进制表示 
int n;
void Floyd()
{
  //d(k)[i][j]：提供i->j连接&&中间点序号不大于k时 = 提供i-j连接&&中间节点序号<k  |  提供i->j连接&&中间节点序号为k(即提供i->k&&提供k->j连接的公司) 
  //d(k)[i][j]=(d[i][j]|(d[i][k]&d[k][j]));
  for(int k=1;k<=n;k++)
  {
  	for(int i=1;i<=n;i++)
  	{
  		for(int j=1;j<=n;j++)
  		{ 
  			d[i][j]|=(d[i][k]&d[k][j]);
  		}
  	}
  }
}
int main()
{
  while(cin>>n&&n)
  {
  	int a,b;
  	memset(d,0,sizeof(d));
  	while(cin>>a>>b&&(a+b))
  	{
  		char s[N];
  		scanf("%s",s);
  		for (size_t i = 0; i < strlen(s); i++)
  		{
  			d[a][b]|=(1<<(s[i]-'a'));//中间节点序号不大于0时(即无中间节点) 
  		}
  	}
  	Floyd();
  	int u,v;
  	while(cin>>u>>v&&(u+v))
  	{
  		bool flag=false; 
  		for(char ch='a';ch<='z';ch++)
  		{
  			if(d[u][v]&(1<<(ch-'a')))
  			{
  				cout<<ch;
  				flag=true;
  			}
  		}
  		if(!flag)
  		cout<<'-';
  		
  		cout<<endl;
  	}
  	cout<<endl;
  }
  return 0;
}