摘要
Title: 3370. 牛年
Tag: spfa
Memory Limit: 64 MB
Time Limit: 1000 ms

3370. 牛年

题意

Farmer John 的奶牛们得知最近正在庆祝牛年的到来时十分兴奋。
牛年总是奶牛们的最爱。
我们知道，中国历法中每一年所对应的生肖遵循 12 年的周期：Ox, Tiger, Rabbit, Dragon, Snake, Horse, Goat, Monkey, Rooster, Dog, Pig, Rat（牛、虎、兔、龙、蛇、马、羊、猴、鸡、狗、猪、鼠），然后回到牛。
奶牛 Bessie 自豪地说她是在许多年前的一个牛年出生的。
她的朋友 Elsie 想要知道她与 Bessie 出生相差多少年，并且希望你能够通过查看农场上若干奶牛出生年份之间的关系来帮助她推算。
思路

第一眼感觉是有负权边的最短路问题，看完别人题解感觉自己想麻烦了

我的思路是将名字先抽象为数值，根据条件进行连负边还是正边，建无向图，从Bessie跑一遍spfa即可

代码

'''
Author: NEFU AB-IN
Date: 2022-03-16 11:49:40
FilePath: \ACM\Acwing\3370.py
LastEditTime: 2022-03-16 14:52:47
'''
from collections import Counter, deque

N = 120
INF = int(2e9)
animals = [
    "Ox", "Tiger", "Rabbit", "Dragon", "Snake", "Horse", "Goat", "Monkey",
    "Rooster", "Dog", "Pig", "Rat"
]
d, idx = Counter(), Counter()
g = [[] for _ in range(N)]
st, dist = [0] * N, [INF] * N
d['Bessie'] = "Ox"  #记录生肖
idx['Bessie'] = 1  #记录编号
cnt = 1


def find(u, v, judge):
    u1 = animals.index(d[u])
    v1 = animals.index(d[v])
    if judge == 'previous':
        if u1 > v1:
            return v1 - (u1 - 12)
        else:
            return v1 - u1 if v1 != u1 else 12

    else:
        if u1 < v1:
            return -(u1 + 12 - v1)
        else:
            return v1 - u1 if v1 != u1 else -12


def spfa():
    q = deque()
    st[1] = 1
    q.appendleft(1)
    dist[1] = 0
    while q:
        u = q.pop()
        st[u] = 0
        for v, w in g[u]:
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                if st[v] == 0:
                    st[v] = 1
                    q.appendleft(v)
    return dist[idx['Elsie']]


n = int(input())
for i in range(n):
    sentence = input().split()
    u, judge, animal, v = sentence[0], sentence[3], sentence[4], sentence[-1]
    d[u] = animal
    cnt += 1
    idx[u] = cnt
    w = find(u, v, judge)
    g[idx[u]].append([idx[v], w])
    g[idx[v]].append([idx[u], -w])

print(abs(spfa()))

3370. 牛年

题意

思路

代码