Submission #54864448

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import networkx as nx
N, M, T = map(int, input().split())
A = tuple(map(int, input().split()))
G = nx.DiGraph()
G.add_nodes_from(range(1, N + 1))
G.add_weighted_edges_from([map(int, input().split()) for _ in range(M)])
L = nx.single_source_dijkstra_path_length(G, 1)
G_inv = G.reverse(copy=False)
L_inv = nx.single_source_dijkstra_path_length(G_inv, 1)
ans = 0
for i in range(1, N + 1):
    if i in L and i in L_inv:
        ans = max(ans, (T - L[i] - L_inv[i]) * A[i - 1])
print(ans)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

import networkx as nx

N, M, T = map(int, input().split())
A = tuple(map(int, input().split()))

G = nx.DiGraph()
G.add_nodes_from(range(1, N + 1))
G.add_weighted_edges_from([map(int, input().split()) for _ in range(M)])
L = nx.single_source_dijkstra_path_length(G, 1)

G_inv = G.reverse(copy=False)
L_inv = nx.single_source_dijkstra_path_length(G_inv, 1)

ans = 0
for i in range(1, N + 1):
    if i in L and i in L_inv:
        ans = max(ans, (T - L[i] - L_inv[i]) * A[i - 1])
print(ans)

Submission Info

Judge Result