P7551 [COCI2020-2021#6] Alias 题解

Naro_Ahgnay · 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;
}