200132025-12-31 01:20:5942Városnézéspypy3Accepted 80/80160ms34524 KiB
from sys import stdin,setrecursionlimit
input=stdin.readline
setrecursionlimit(10**6)

def solv():
    N,M = map(int,input().split())
    P = [0]+list(map(int,input().split()))
    G = [set() for i in range(N+1)]
    Ginv = [set() for i in range(N+1)]
    for i in range(M):
        x,y = map(int,input().split())
        G[x].add(y)
        Ginv[y].add(x)
    visited={N}
    cur=[N]
    while cur:
        tmp=set()
        for v in cur:
            for w in Ginv[v]:
                if w not in visited:
                    tmp.add(w)
                    visited.add(w)
        cur=tmp
    if 1 not in visited:
        print(-1)
        return
    #print(visited,Ginv)
    for v in visited:
        tmp=[]
        for w in G[v]:
            if w not in visited:
                tmp.append(w)
        for w in tmp:
            G[v].remove(w)
    #print(G)
    res=[0]*(N+1)
    reached=[False]*(N+1)
    res[N]=P[N]
    reached[N]=True
    cur=[N]
    def rek(i):
        cur=-1
        for v in G[i]:
            if reached[v]:
                cur=max(cur,res[v]+P[i])
            else:
                rek(v)
                cur=max(cur,res[v]+P[i])
        reached[i]=True
        res[i]=cur
    rek(1)
    """
    while cur:
        tmp=set()
        for v in cur:
            if reached[v]<len(G[v]):
                tmp.add(v)
                continue
            for w in Ginv[v]:
                res[w]=max(res[w],res[v]+P[w])
                reached[w]+=1
                tmp.add(w)
        cur=tmp
    """
    print(res[1])
    RES=[1]
    while RES[-1]!=N:
        for v in G[RES[-1]]:
            if res[v]+P[RES[-1]]==res[RES[-1]]:
                RES.append(v)
                break
    print(*RES)

solv()
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted46ms19692 KiB
subtask220/20
2Accepted43ms19792 KiB
3Accepted39ms19864 KiB
4Accepted39ms19856 KiB
5Accepted68ms22708 KiB
6Accepted67ms22656 KiB
7Accepted64ms24500 KiB
8Accepted72ms24284 KiB
9Accepted43ms21212 KiB
10Accepted116ms34208 KiB
11Accepted45ms19820 KiB
12Accepted46ms19832 KiB
subtask325/25
13Accepted43ms19804 KiB
14Accepted39ms19684 KiB
15Accepted39ms19676 KiB
16Accepted48ms21076 KiB
17Accepted45ms19684 KiB
18Accepted43ms21204 KiB
19Accepted39ms19932 KiB
20Accepted45ms19816 KiB
21Accepted39ms19936 KiB
22Accepted71ms22120 KiB
23Accepted54ms21580 KiB
24Accepted68ms22748 KiB
25Accepted59ms22236 KiB
26Accepted65ms22268 KiB
27Accepted71ms22592 KiB
28Accepted123ms27248 KiB
29Accepted83ms23516 KiB
30Accepted142ms27780 KiB
31Accepted101ms25364 KiB
32Accepted96ms28020 KiB
33Accepted68ms24284 KiB
subtask420/20
34Accepted39ms19832 KiB
35Accepted43ms19852 KiB
36Accepted43ms19876 KiB
37Accepted39ms19916 KiB
38Accepted50ms21068 KiB
39Accepted41ms19900 KiB
40Accepted48ms21288 KiB
41Accepted41ms20144 KiB
42Accepted46ms19988 KiB
43Accepted46ms19960 KiB
44Accepted43ms21124 KiB
45Accepted39ms19672 KiB
46Accepted50ms21112 KiB
47Accepted48ms21124 KiB
48Accepted48ms21148 KiB
49Accepted45ms21068 KiB
50Accepted39ms19712 KiB
51Accepted39ms19896 KiB
52Accepted43ms19732 KiB
53Accepted43ms19888 KiB
54Accepted45ms19684 KiB
55Accepted41ms19872 KiB
56Accepted43ms19756 KiB
57Accepted37ms19916 KiB
58Accepted41ms20156 KiB
59Accepted45ms19936 KiB
60Accepted43ms19688 KiB
61Accepted39ms19684 KiB
62Accepted45ms19984 KiB
63Accepted45ms19732 KiB
64Accepted39ms19928 KiB
65Accepted39ms19692 KiB
66Accepted39ms19940 KiB
subtask515/15
67Accepted39ms19832 KiB
68Accepted43ms19792 KiB
69Accepted39ms19864 KiB
70Accepted39ms19856 KiB
71Accepted68ms22708 KiB
72Accepted67ms22656 KiB
73Accepted64ms24500 KiB
74Accepted72ms24284 KiB
75Accepted43ms21212 KiB
76Accepted116ms34208 KiB
77Accepted45ms19820 KiB
78Accepted46ms19832 KiB
79Accepted43ms19804 KiB
80Accepted39ms19684 KiB
81Accepted39ms19676 KiB
82Accepted48ms21076 KiB
83Accepted45ms19684 KiB
84Accepted43ms21204 KiB
85Accepted39ms19932 KiB
86Accepted45ms19816 KiB
87Accepted39ms19936 KiB
88Accepted71ms22120 KiB
89Accepted54ms21580 KiB
90Accepted68ms22748 KiB
91Accepted59ms22236 KiB
92Accepted65ms22268 KiB
93Accepted71ms22592 KiB
94Accepted123ms27248 KiB
95Accepted83ms23516 KiB
96Accepted142ms27780 KiB
97Accepted101ms25364 KiB
98Accepted96ms28020 KiB
99Accepted68ms24284 KiB
100Accepted43ms19852 KiB
101Accepted43ms19876 KiB
102Accepted39ms19916 KiB
103Accepted50ms21068 KiB
104Accepted41ms19900 KiB
105Accepted48ms21288 KiB
106Accepted41ms20144 KiB
107Accepted46ms19988 KiB
108Accepted46ms19960 KiB
109Accepted43ms21124 KiB
110Accepted39ms19672 KiB
111Accepted50ms21112 KiB
112Accepted48ms21124 KiB
113Accepted48ms21148 KiB
114Accepted45ms21068 KiB
115Accepted39ms19712 KiB
116Accepted39ms19896 KiB
117Accepted43ms19732 KiB
118Accepted43ms19888 KiB
119Accepted45ms19684 KiB
120Accepted41ms19872 KiB
121Accepted43ms19756 KiB
122Accepted37ms19916 KiB
123Accepted41ms20156 KiB
124Accepted45ms19936 KiB
125Accepted43ms19688 KiB
126Accepted39ms19684 KiB
127Accepted45ms19984 KiB
128Accepted45ms19732 KiB
129Accepted39ms19928 KiB
130Accepted39ms19692 KiB
131Accepted39ms19940 KiB
132Accepted59ms21980 KiB
133Accepted50ms21416 KiB
134Accepted57ms21940 KiB
135Accepted59ms21648 KiB
136Accepted71ms22144 KiB
137Accepted61ms21844 KiB
138Accepted52ms21992 KiB
139Accepted57ms22520 KiB
140Accepted74ms24280 KiB
141Accepted59ms22672 KiB
142Accepted71ms25820 KiB
143Accepted148ms30172 KiB
144Accepted71ms27092 KiB
145Accepted112ms28384 KiB
146Accepted90ms32672 KiB
147Accepted160ms34524 KiB
148Accepted138ms31156 KiB
149Accepted104ms28308 KiB