自动搬运

查看原文

来自洛谷，原作者为

	Naro_Ahgnay 值得就喜欢。

搬运于2025-08-24 22:30:56，当前版本为作者最后更新于2022-01-05 19:24:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

给定 $m$ 对字符串，每对字符串有 $x$ 和 $y$ 以及 $t$，表示如果他记起或听到了单词 $x$，他会在 $t$ 毫秒后记起单词 $y$。可以将其理解为从 $x$ 到 $y$ 有一条边权为 $t$ 的单向边。

然后输入一个 $q$ 表示有 $q$ 轮，每轮有一对字符串 $a$ 和 $b$,求出从初始单词 $a$ 到多少毫秒后会记起目标单词 $b$。可以将其理解为求从 $a$ 到 $b$ 的最短路。

思路

通过对题目的分析后我们发现，这道题的本质就是求最短路。不会最短路算法的同学先移步此处。

P3371 【模板】单源最短路径（弱化版）

P4779 【模板】单源最短路径（标准版）

然而由于输入的是字符串，为了方便，我们要将字符串转换为带编号的点。直接用 map 将字符串映射成点即可。

定义 map 类型：

map<string,int> mp;

意思是将一个字符串类型的变量用一个整型变量来表示。

使用 map 映射：

string s="ABC"
mp[s]=1

意思是将一个字符串类型的变量 $s$ 用 $1$ 来表示。

mp.count(s)

表示检查字符串类型 $s$ 是否在 map 类型中已经被映射。

通过以上将字符串映射到编号的操作，剩下的就是最短路的板子了。建议使用时间复杂度较低的 Dijkstra 算法，通过堆优化可以实现 $\Theta{(n\log(n+m))}$ 的时间复杂度。

code

#include<cstdio>
#include<iostream>
#include<utility>
#include<string>
#include<cstring>
#include<queue>
#include<map>
using namespace std;
struct node{
	int next,to;
	long long dis;
}e[10001];
int n,m,ne,p,q;
int h[10001];
long long dis[1001],t;
bool vis[1001];
string a,b;
map<string,int> ma;
void add(int u,int v,long long w)
{
	e[++ne].next=h[u];
	e[ne].dis=w,e[ne].to=v,h[u]=ne;
}
void dij(int s)
{
	for(int i=1;i<=n;i++) dis[i]=1e14;
	memset(vis,0,sizeof(vis));
	priority_queue<pair<long long,int> > qu;
	qu.push(make_pair(0,s));
	dis[s]=0;
	while(!qu.empty())
	{
		int u,v;
		u=qu.top().second;qu.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=h[u];i;i=e[i].next)
		{
			v=e[i].to;
			if(dis[v]>dis[u]+e[i].dis)
			{
				dis[v]=dis[u]+e[i].dis;
				qu.push(make_pair(-dis[v],v));
			}
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		cin>>a>>b>>t;
		if(!ma.count(a)) ma[a]=++p;
		if(!ma.count(b)) ma[b]=++p;
		add(ma[a],ma[b],t);
	}
	scanf("%d",&q);
	while(q--)
	{
		cin>>a>>b;
		int g1,g2;
		g1=ma[a],g2=ma[b];
		dij(g1);
		if(dis[g2]==1e14) printf("Roger\n");
		else printf("%lld\n",dis[g2]);
	}
	return 0;
}