8.2万

1847497680

DarksideCoder

Magic_KID
upup
AcKing_HIT

15084948533

JayZ
joykiller

QAQlzy

1个月前
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int MAX_N = 20000005;       // 最长字符串长度

int P[MAX_N];       // P[i]表示以i位置为中心的最长回文子串长度
char __s[MAX_N];

// 返回最长回文子串长度
char ss[MAX_N * 2 + 5];
int manacher(char* s) {
int n = strlen(s);
if (n <= 1) {
return n;
}

// 构造新字符串
for (int i = 0; i < 2*n+1; i++) {
if (i & 1) {
ss[i] = s[i>>1];
} else {
ss[i] = '#';
}
}

P[0] = 1;
int L = 0, R = 0;       // 当前已经找到的所有回文子串中结束位置最靠右的回文子串的左右边界
int max_r = 1;
for (int i = 1; i < 2*n+1; i++) {
if (i > R) {
int ll = i, rr = i;
while (ll-1 >= 0 && rr+1 < 2*n+1 && ss[ll-1] == ss[rr+1]) {
ll--, rr++;
}
P[i] = rr - i + 1;
} else {
int j = L + R - i;
int l_bound = j - P[j] + 1;
if (l_bound > L) {
P[i] = P[j];
} else if (l_bound < L) {
P[i] = R - i + 1;
} else {
int ll = i-P[j]+1, rr = i+P[j]-1;
while (ll-1 >= 0 && rr+1 < 2*n+1 && ss[ll-1] == ss[rr+1]) {
ll--, rr++;
}
P[i] = rr - i + 1;
}
}

if (i + P[i] - 1 > R) {
R = i + P[i] - 1;
L = i - P[i] + 1;
}

max_r = max(max_r, P[i]);
}

return max_r - 1;
}

int main(void) {
scanf("%s", __s);
printf("%d\n", manacher(__s));
return 0;
}



1个月前


#include <vector>
#include <stdio.h>
#include <string.h>
using namespace std;

const int MAX_TWO_SAT_N = 1000005 * 2;
const int MAX_TWO_SAT_M = MAX_TWO_SAT_N * 2;
const int INF = 0x3f3f3f3f;

int __two_sat_h[MAX_TWO_SAT_N], __two_sat_ne[MAX_TWO_SAT_M], __two_sat_e[MAX_TWO_SAT_M];
int __two_sat_dfn[MAX_TWO_SAT_N], __two_sat_low[MAX_TWO_SAT_N];
int __two_sat_node2sccid[MAX_TWO_SAT_N], __two_sat_visit[MAX_TWO_SAT_N];

struct edge {
int a, b;
};

class TWO_SAT {
public:
TWO_SAT(int n, vector<edge>& edges) : node_n(n), h(__two_sat_h), ne(__two_sat_ne), e(__two_sat_e),
dfn(__two_sat_dfn), low(__two_sat_low), node2sccid(__two_sat_node2sccid),
visit(__two_sat_visit), idx(0), time_v(0), scc_id_cnt(1) {
memset(h, -1, sizeof(int) * (node_n*2 + 1));
for (int i = 0; i < edges.size(); i++) {
int a = edges[i].a, b = edges[i].b;

int aa = a < 0 ? -a : a+n;
int bb = b < 0 ? -b+n : b;

aa = a < 0 ? -a+n : a;
bb = b < 0 ? -b : b+n;
}
}

bool get_solution(int* ans) {
int max_node_num = node_n * 2;
memset(dfn, 0x3f, sizeof(int) * (max_node_num + 1));
memset(low, 0x3f, sizeof(int) * (max_node_num + 1));
memset(node2sccid, 0, sizeof(int) * (max_node_num + 1));
memset(visit, 0, sizeof(int) * (max_node_num + 1));

time_v = 0;
buf.clear();
scc_id_cnt = 1;

for (int node = 1; node <= max_node_num; node++) {
if (h[node] == -1) {
continue;
}

if (dfn[node] == INF) {
__dfs(node);
}
}

memset(ans, 0, sizeof(int) * (node_n + 1));
for (int node = 1; node <= node_n; node++) {
if (node2sccid[node] == node2sccid[node+node_n] && node2sccid[node] != 0) {
return false;
}

if (node2sccid[node] < node2sccid[node+node_n]) {
ans[node] = 1;
}
}

return true;
}

private:
int node_n;
int *h, *ne, *e;
int *dfn, *low;
int *node2sccid;
int *visit;
int idx;
int time_v;
int scc_id_cnt;
vector<int> buf;

void __add_edge(int a, int b) {
ne[idx] = h[a], e[idx] = b; h[a] = idx++;
}

void __dfs(int cur) {
time_v++;
dfn[cur] = low[cur] = time_v;
buf.push_back(cur);

int pos = buf.size() - 1;
for (int i = h[cur]; ~i; i = ne[i]) {
int next = e[i];
if (visit[next]) {
continue;
}

if (dfn[next] == INF) {
__dfs(next);
low[cur] = min(low[cur], low[next]);
} else {
low[cur] = min(low[cur], dfn[next]);
}
}

if (low[cur] == dfn[cur]) {
while (buf.size() > pos) {
int node = buf.back(); buf.pop_back();
node2sccid[node] = scc_id_cnt;
visit[node] = 1;
}
scc_id_cnt += 1;
}
}

};

int ans[1000005];

int main() {
int n, m;
int a, b, v1, v2;
scanf("%d %d", &n, &m);

vector<edge> edges;
while (m--) {
scanf("%d %d %d %d", &a, &v1, &b, &v2);
if (v1 == 0) {
a = -a;
}

if (v2 == 0) {
b = -b;
}

edges.push_back({a, b});
}

TWO_SAT algo(n, edges);
if (algo.get_solution(ans)) {
printf("POSSIBLE\n");
for (int i = 1; i <= n; i++) {
printf("%d ", ans[i]);
}
} else {
printf("IMPOSSIBLE\n");
}

return 0;
}



3个月前


#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;

int arr[1005];
int cache1[1005][1005];
int cache2[1005][1005];

int right(int i, int j);
int left(int i, int j) {
if (cache1[i][j] != -1) {
return cache1[i][j];
}

if (i == j) {
return arr[i];
}

int& ret = cache1[i][j];
int X = arr[j], L = left(i, j-1), R = right(i, j-1);
if (X == R) {
return ret = 0;
}

if (X < L && X < R) {
return ret = X;
}

if (X > L && X > R) {
return ret = X;
}

if (L > R) {
return ret = X - 1;
} else {
return ret = X + 1;
}
}

int right(int i, int j) {
if (cache2[i][j] != -1) {
return cache2[i][j];
}

if (i == j) {
return arr[i];
}

int& ret = cache2[i][j];
int X = arr[i], L = left(i+1, j), R = right(i+1, j);
if (X == L) {
return ret = 0;
}

if (X < L && X < R) {
return ret = X;
}

if (X > L && X > R) {
return ret = X;
}

if (L < R) {
return ret = X - 1;
} else {
return ret = X + 1;
}
}

int main(void) {
int T, n;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", arr+i);
}

if (n == 1) {
printf("1\n");
continue;
}

memset(cache1, -1, sizeof(cache1));
memset(cache2, -1, sizeof(cache2));
if (arr[0] == left(1, n-1)) {
printf("0\n");
} else {
printf("1\n");
}

}

return 0;
}



3个月前


#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;

int arr[1005];
int cache1[1005][1005];
int cache2[1005][1005];

int right(int i, int j);
int left(int i, int j) {
if (cache1[i][j] != -1) {
return cache1[i][j];
}

if (i == j) {
return arr[i];
}

int& ret = cache1[i][j];
int X = arr[j], L = left(i, j-1), R = right(i, j-1);
if (X == R) {
return ret = 0;
}

if (X < L && X < R) {
return ret = X;
}

if (X > L && X > R) {
return ret = X;
}

if (L > R) {
return ret = X - 1;
} else {
return ret = X + 1;
}
}

int right(int i, int j) {
if (cache2[i][j] != -1) {
return cache2[i][j];
}

if (i == j) {
return arr[i];
}

int& ret = cache2[i][j];
int X = arr[i], L = left(i+1, j), R = right(i+1, j);
if (X == L) {
return ret = 0;
}

if (X < L && X < R) {
return ret = X;
}

if (X > L && X > R) {
return ret = X;
}

if (L < R) {
return ret = X - 1;
} else {
return ret = X + 1;
}
}

int main(void) {
int T, n;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", arr+i);
}

if (n == 1) {
printf("1\n");
continue;
}

memset(cache1, -1, sizeof(cache1));
memset(cache2, -1, sizeof(cache2));
if (arr[0] == left(1, n-1)) {
printf("0\n");
} else {
printf("1\n");
}

}

return 0;
}


3个月前


'''

'''

def get_prime(N):
prime_vals = []
flag = [True] * (N+1)
for val in range(2, N+1):
if flag[val]:
prime_vals.append(val)

for p_val in prime_vals:
if val * p_val > N:
break

flag[val * p_val] = False

if val % p_val == 0:
break

return prime_vals

primes = get_prime(100000)

# 分解质因数函数，返回元组数组[ (质因子1, 次幂1)， (质因子2, 次幂2)， (质因子3, 次幂3) ...... ]
# 质因子的数值升序排列
def devide_prime(val):
ans = []

for i in primes:
if i*i > val:
break

if val % i == 0:
cnt = 0
while val % i == 0:
val //= i
cnt += 1

ans.append((i, cnt))

if val == 1:
break

# 特判最后可能剩下的大于sqrt(val)的最大的质因子
if val != 1:
ans.append((val, 1))

return ans

# 获取所有约数的函数
def get_approximate_numbers(val):
ans = []
primes = devide_prime(val)

def dfs(idx, prev_val):
if prev_val*prev_val > val:
return

if idx >= len(primes):
ans.append(prev_val)
if val // prev_val != prev_val:
ans.append(val // prev_val)

return

base = None
for pow_val in range(primes[idx][1]+1):
if pow_val == 0:
base = 1
else:
base *= primes[idx][0]

dfs(idx+1, prev_val * base)
dfs(0, 1)

return ans

def gcd(a, b):
if a > b:
a, b, = b, a

while a:
a, b = b % a, a
return b

n = int(input())
for _ in range(n):
a0, a1, b0, b1 = map(int, input().split())
app_vals = get_approximate_numbers(b1)

cnt = 0
for app_val in app_vals:
if b0 * app_val == b1 * gcd(app_val, b0):
if gcd(app_val, a0) == a1:
cnt += 1

print(cnt)



3个月前


# import sys
# sys.stdin = open("data.txt", "r")

'''

'''

from collections import deque
from functools import lru_cache

class AcTrieNode:
def __init__(self, fa):
self.s = ''             # end节点自己本身的单词
self.fail_s = []        # fail指针指向的节点序列的单词列表(如果fail指针指向的节点是一个end节点，此字段保存所有这些单词的列表)
self.next = {}          # 边和子节点映射
self.is_end = False     # 是否是end节点
self.fail = None        # ac自动机的fail指针
self.fa = fa            # 父节点指针
self.id = 0             # 节点的id号

class AcTrie:
def __init__(self):
self.root = AcTrieNode(None)
self.__idx = 1

def append(self, s: str):
cur = self.root
for ch in s:
if ch not in cur.next:
new_node = AcTrieNode(cur)
new_node.id = self.__idx
self.__idx += 1

new_node.s = cur.s + ch
cur.next[ch] = new_node

cur = cur.next[ch]
cur.is_end = True

# 构建ac自动机接口
def build(self, s_list = []):
# 第一步是构建普通的Trie
for s in s_list:
self.append(s)

# 层次遍历构建Fail指针
que = deque()
que.append(self.root)

depth = 0
while len(que) > 0:
node_num = len(que)

for _ in range(node_num):
cur = que.popleft()
if depth == 1:
# 根节点下面的第一层word长度是1，是没有后缀的，fail指针全部指向root
cur.fail = self.root
elif depth != 0:
cur.fail = self.root

# 循环找最长后缀的候选
p = cur.fa.fail
last_ch = cur.s[-1]
while True:
if not p:
break

if last_ch in p.next:
cur.fail = p.next[last_ch]

f = cur.fail
if f.is_end:
# 如果fail指针指向的节点是一个end节点，或者这个节点的fail_s列表不为空，需要添加这些单词到cur节点的fail_s列表中
cur.fail_s.append(f.s)

# fail指针指向的节点中fail_s里面的单词必须全部继承下来，因为这些单词也是后缀的备选
for s in f.fail_s:
cur.fail_s.append(s)

break
else:
p = p.fail

for new_node in cur.next.values():
que.append(new_node)

depth += 1

# 获取节点状态转移的表 [0号点转移表，1号点转移表, ......]
def get_stat_map(self):
ans = [{'A':None, 'G':None, 'C':None, 'T':None} for _ in range(self.__idx)]

def dfs(node: AcTrieNode):
for ch in 'AGCT':
if ch in node.next:
if node.next[ch].is_end or len(node.next[ch].fail_s) != 0:
# 发生了匹配，下一个字符不可能是ch
ans[node.id][ch] = None
else:
ans[node.id][ch] = node.next[ch].id

else:
cur = node
while True:
if ch in cur.next:
if cur.next[ch].is_end or len(cur.next[ch].fail_s) != 0:
# 发生了匹配，下一个字符不可能是ch
ans[node.id][ch] = None
else:
ans[node.id][ch] = cur.next[ch].id

break

else:
if cur.fail is not None:
cur = cur.fail
else:
ans[node.id][ch] = cur.id
break

for child in node.next.values():
dfs(child)

dfs(self.root)
return ans

case_id = 1
while True:
n = int(input())
if n == 0:
break

ac_trie = AcTrie()

for _ in range(n):
ac_trie.append(input())

ac_trie.build()
stat_map = ac_trie.get_stat_map()

s = input().strip()
cache = [[None]*(len(s)+1) for _ in range(20*n)]
n = len(s)

# dp(stat, ii)表示Ac自动机状态为stat情况下，继续构造出一个合法的字符串[ii:n]这一段的最少需要修改的次数
def dp(stat, ii):
if ii == n:
return 0

if cache[stat][ii] is not None:
return cache[stat][ii]

ans = 0x7fffffff
for ch in 'AGCT':
if stat_map[stat][ch] is None:
continue

t = 0
if s[ii] != ch:
t += 1

t += dp(stat_map[stat][ch], ii+1)
ans = min(ans, t)

# print(stat, ii, ans, n)
cache[stat][ii] = ans
return ans

ans = dp(ac_trie.root.id, 0)
print(f'Case {case_id}: {ans if ans != 0x7fffffff else -1}')
case_id += 1



3个月前


# import sys
# sys.stdin = open("data.txt", "r")

'''

'''

from collections import deque
from functools import lru_cache

class AcTrieNode:
def __init__(self, fa):
self.s = ''
self.fail_s = []
self.next = {}
self.is_end = False
self.fail = None
self.fa = fa
self.id = 0

class AcTrie:
def __init__(self):
self.root = AcTrieNode(None)
self.__idx = 1

def append(self, s: str):
cur = self.root
for ch in s:
if ch not in cur.next:
new_node = AcTrieNode(cur)
new_node.id = self.__idx
self.__idx += 1

new_node.s = cur.s + ch
cur.next[ch] = new_node

cur = cur.next[ch]
cur.is_end = True

def build(self, s_list = []):
for s in s_list:
self.append(s)

que = deque()
que.append(self.root)

depth = 0
while len(que) > 0:
node_num = len(que)

for _ in range(node_num):
cur = que.popleft()
if depth == 1:
cur.fail = self.root
elif depth != 0:
cur.fail = self.root

p = cur.fa.fail
last_ch = cur.s[-1]
while True:
if not p:
break

if last_ch in p.next:
cur.fail = p.next[last_ch]

f = cur.fail
if f.is_end:
cur.fail_s.append(f.s)

for s in f.fail_s:
cur.fail_s.append(s)

break
else:
p = p.fail

for new_node in cur.next.values():
que.append(new_node)

depth += 1

# 获取节点状态转移的表 [0号点转移表，1号点转移表, ......]
def get_stat_map(self):
ans = [{'A':None, 'G':None, 'C':None, 'T':None} for _ in range(self.__idx)]

def dfs(node: AcTrieNode):
for ch in 'AGCT':
if ch in node.next:
if node.next[ch].is_end or len(node.next[ch].fail_s) != 0:
# 发生了匹配，下一个字符不可能是ch
ans[node.id][ch] = None
else:
ans[node.id][ch] = node.next[ch].id

else:
cur = node
while True:
if ch in cur.next:
if cur.next[ch].is_end or len(cur.next[ch].fail_s) != 0:
# 发生了匹配，下一个字符不可能是ch
ans[node.id][ch] = None
else:
ans[node.id][ch] = cur.next[ch].id

break

else:
if cur.fail is not None:
cur = cur.fail
else:
ans[node.id][ch] = cur.id
break

for child in node.next.values():
dfs(child)

dfs(self.root)
return ans

case_id = 1
while True:
n = int(input())
if n == 0:
break

ac_trie = AcTrie()

for _ in range(n):
ac_trie.append(input())

ac_trie.build()
stat_map = ac_trie.get_stat_map()

s = input().strip()
cache = [[None]*(len(s)+1) for _ in range(20*n)]
n = len(s)

# dp(stat, ii)表示Ac自动机状态为stat情况下，继续构造出一个合法的字符串[ii:n]这一段的最少需要修改的次数
def dp(stat, ii):
if ii == n:
return 0

if cache[stat][ii] is not None:
return cache[stat][ii]

ans = 0x7fffffff
for ch in 'AGCT':
if stat_map[stat][ch] is None:
continue

t = 0
if s[ii] != ch:
t += 1

t += dp(stat_map[stat][ch], ii+1)
ans = min(ans, t)

# print(stat, ii, ans, n)
cache[stat][ii] = ans
return ans

ans = dp(ac_trie.root.id, 0)
print(f'Case {case_id}: {ans if ans != 0x7fffffff else -1}')
case_id += 1



3个月前


import sys

'''
S(i) 表示开始工作时间小于等于i的雇佣员工的总数

1. S(i) >= S(i-1) (i=1,2,3,4,....23)
2. S(0) >= 0

3. S(i) + S(23) - S(i+16) >= arr[i]

3. S(i) - S(i-8) >= arr[i]

4. S(i) - S(i-1) <= cnt[i], cnt[i]是从i时间开始工作的人的数量

'''

from collections import Counter
from collections import deque

class SPFA:

# start_node 为起始点，edges是边的三元组(节点1， 节点2， 边权重) is_directed表示是否是有向图
# 包含节点为1, 2, 3, 4, ..... max_node_num
def __init__(self, start_node, edges, is_directed, max_node_num):
self.edges = edges[::]
self.start_node = start_node
self.is_directed = is_directed
self.max_node_num = max_node_num

# 获取最短路径长度的列表[(节点1，长度1), (节点2, 长度2) .....]
def getMinPathLen(self):
return self.getInfo(min_path=True)

# 获取最长路径长度列表[(节点1，长度1), (节点2, 长度2) .....]
def getMaxPathLen(self):
return self.getInfo(min_path=False)

# min_path表示求的是最短路径还是最长路径
def getInfo(self, min_path = True):
dis = [0x7fffffff] * (self.max_node_num+1) if min_path else [-0x7fffffff] * (self.max_node_num+1)
dis[self.start_node] = 0

for a, b, w in self.edges:
if not self.is_directed:
# 无向图检查是否有负边
if (min_path == True and w < 0) and (min_path == False and w > 0):
# 有正环或者负环提前退出
return None

else:

updated_nodes = deque()
updated_nodes.append(self.start_node)
in_que = [0] * (self.max_node_num + 1)
in_que[self.start_node] = 1

# 进行V次迭代，第V次检查是否是无解情况
iter_times = 0
while iter_times < self.max_node_num:
update_flag = False

# 利用上一轮迭代距离变小的点进行松弛操作
node_num = len(updated_nodes)
for _ in range(node_num):
a = updated_nodes.popleft()
in_que[a] = 0
continue

if dis[a] == 0x7fffffff:
if w == -0x7fffffff:
new_dis = 0
else:
new_dis = 0x7fffffff

elif dis[a] == -0x7fffffff:
if w == 0x7fffffff:
new_dis = 0
else:
new_dis = -0x7fffffff
else:
new_dis = dis[a] + w

if (min_path == True and new_dis < dis[b]) or (min_path == False and new_dis > dis[b]):
dis[b] = new_dis
update_flag = True

if in_que[b] == 0:
in_que[b] = 1
updated_nodes.append(b)

iter_times += 1

if iter_times == self.max_node_num:
if update_flag:
return None

if not update_flag:
break

return [[node, dis[node]] for node in range(1, self.max_node_num+1)]

t = int(input())
for _ in range(t):
arr = list( map(int, input().split()) )
n = int(input())
possible = [0] * 24
for i in range(n):
possible[int(input())] += 1

if sum(possible) == 0:
print(0)
else:
find_ans = False
min_cost = 0x7fffffff
for S23 in range(0, n+1):
# 为了方便计算，所有数值下标都往后移动了一个位置, 超级源点已定义为23, 实际存储时候用24的位置
edges = []

# S(i) >= S(i-1) (i=1,2,3,4,....22)
for i in range(1, 23):
edges.append((i-1+1, i+1, 0))

# S(22) <= S(23)
edges.append((24, 22+1, 0))

# S(i) >= S(i+16) - S23 + arr[i]
for i in range(8):
edges.append((i+16+1, i+1, arr[i]-S23))

# S(i) >= S(i-8) + arr[i]
for i in range(8, 23):
edges.append((i-8+1, i+1, arr[i]))

# S(23) - S(15) >= arr[23], S(15) <= S(23) - arr[23]
edges.append((15+1, 24, -(S23 - arr[23])))

# S(0) <= possible[0]
edges.append((0+1, 24, -possible[0]))

# S(i) - S(i-1) <= possible[i] i = 1, 2, 3..... 22
for i in range(1, 23):
edges.append((i+1, i-1+1, -possible[i]))

# S(23) - S(22) <= possible[23] => S(22) >= S(23) - possible[23]
edges.append((24, 22+1, S23 - possible[23]))

# 虚拟源点向所有点添加边 S(i) >= 0, i = 0, 1, 2, ..... 22
for i in range(23):
edges.append((24, i+1, 0))

algo = SPFA(24, edges, is_directed=True, max_node_num=24)
ans = algo.getMaxPathLen()
if ans is None:
continue

find_ans = True
min_cost = min(min_cost, S23)

if find_ans:
print(min_cost)
else:
print('No Solution')



3个月前

import sys

'''

'''

from collections import deque

class SPFA:

# start_node 为起始点，edges是边的三元组(节点1， 节点2， 边权重) is_directed表示是否是有向图
# 包含节点为1, 2, 3, 4, ..... max_node_num
def __init__(self, start_node, edges, is_directed, max_node_num):
self.edges = edges[::]
self.start_node = start_node
self.is_directed = is_directed
self.max_node_num = max_node_num

# 获取最短路径长度的列表[(节点1，长度1), (节点2, 长度2) .....]
def getMinPathLen(self):
return self.getInfo(min_path=True)

# 获取最长路径长度列表[(节点1，长度1), (节点2, 长度2) .....]
def getMaxPathLen(self):
return self.getInfo(min_path=False)

# min_path表示求的是最短路径还是最长路径
def getInfo(self, min_path = True):
dis = [0x7fffffff] * (self.max_node_num+1) if min_path else [-0x7fffffff] * (self.max_node_num+1)
dis[self.start_node] = 0

for a, b, w in self.edges:
if not self.is_directed:
# 无向图检查是否有负边
if (min_path == True and w < 0) and (min_path == False and w > 0):
# 有正环或者负环提前退出
return None

else:

updated_nodes = deque()
updated_nodes.append(self.start_node)
in_que = [0] * (self.max_node_num + 1)
in_que[self.start_node] = 1

# 进行V次迭代，第V次检查是否是无解情况
iter_times = 0
cnt = [0] * (self.max_node_num + 1)
while iter_times < self.max_node_num:
update_flag = False

# 利用上一轮迭代距离变小的点进行松弛操作
node_num = len(updated_nodes)
for _ in range(node_num):
a = updated_nodes.popleft()
in_que[a] = 0
continue

if dis[a] == 0x7fffffff:
if w == -0x7fffffff:
new_dis = 0
else:
new_dis = 0x7fffffff

elif dis[a] == -0x7fffffff:
if w == 0x7fffffff:
new_dis = 0
else:
new_dis = -0x7fffffff
else:
new_dis = dis[a] + w

if (min_path == True and new_dis < dis[b]) or (min_path == False and new_dis > dis[b]):
dis[b] = new_dis
cnt[b] = cnt[a] + 1
update_flag = True

if cnt[b] >= self.max_node_num:
return None

if in_que[b] == 0:
in_que[b] = 1
updated_nodes.append(b)

iter_times += 1

if iter_times == self.max_node_num:
if update_flag:
return None

if not update_flag:
break

return dis

edges = []
n, m1, m2 = map(int, input().split())
for i in range(m1):
a, b, w = map(int, input().split())
if a > b:
a, b = b, a

# val(b) - val(a) <= w
edges.append((a, b, w))

for i in range(m2):
a, b, w = map(int, input().split())
if a > b:
a, b = b, a

# val(b) - val(a) >= w
edges.append((b, a, -w))

for i in range(2, n+1):
# 后一个要大于等于前一个
# val(i) >= val(i-1)
edges.append((i, i-1, 0))

# 从2开始的每一个点都小于等于一个极大值，这样才能让超级源点对每一个点都是可达的，注意这里不能取0x7fffffff, 这个数值表示的是不可达
edges.append((n+1, i, 0x7ffffffe))

# 超级源点是n+1, 要求1号点固定在0位置
edges.append((1, n+1, 0))
edges.append((n+1, 1, 0))

# print(edges)
algo = SPFA(n+1, edges, is_directed=True, max_node_num=n+1)
ans = algo.getMinPathLen()
if ans is None:
print(-1)
else:
if ans[n] == 0x7ffffffe:
print(-2)
else:
print(ans[n])



4个月前
cache = [[None]* 1005 for _ in range(1005)]

# dp(i, j)表示用小于等于j的数凑i的所有方案的数量
def dp(i, j):
if i == 0:
return 1

if j == 1:
return 1

if cache[i][j] is not None:
return cache[i][j]

if j > i:
ans = dp(i, i)
else:
ans = dp(i-j, j) + dp(i, j-1)

cache[i][j] = ans % 1000000007
return ans % 1000000007

n = int(input())
print(dp(n, n))