248482026-02-16 02:30:37999Városnézéscpp17Runtime error 0/80532ms262144 KiB
// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main() {
    int n,m;cin>>n>>m;
    vector<vector<int>> v(n),g(n);
    vector<int> lat(n),fok(n);
    for(int i = 0;i<n;i++){
        cin>>lat[i];
    }
    for(int i = 0;i<m;i++){
        int a,b;cin>>a>>b;
        a--;b--;
        v[a].push_back(b);
        g[b].push_back(a);
        fok[a]++;
    }
    vector<int> dp(n,-1);
    queue<int> q;
    for(int i = 0;i<n;i++){
        if(fok[i]==0&&i!=n-1){
            q.push(i);
            dp[i]=-2;
        }
        else if(fok[i]==0&&i==n-1){
            dp[i]=0;
            q.push(i);
        }
    }
    while(!q.empty()){
        int a=q.front();
        q.pop();
        if(dp[a]!=-2)for(int u:v[a])dp[a]=max(dp[a],dp[u]);
        if(dp[a]!=-2)dp[a]+=lat[a];
        for(int u : g[a]){
            fok[u]--;
            if(fok[u]==0){
                q.push(u);
            }
        }
    }
    //for(int i : dp)cout<<i<<' ';return 0;
    if(dp[0]<0){
        cout<<-1;
        return 0;
    }
    cout<<dp[0]<<endl;
    int i = 0;
    vector<int> ans;
    while(i!=n-1){
        ans.push_back(i+1);
        for(int u : v[i]){
            if(dp[u]+lat[i]==dp[i]){
                i=u;
                break;
            }
        }
    }
    ans.push_back(n);
    for(int i : ans)cout<<i<<' ';
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
subtask20/20
2Accepted1ms316 KiB
3Accepted1ms316 KiB
4Runtime error412ms262144 KiB
5Runtime error521ms262144 KiB
6Runtime error518ms262144 KiB
7Runtime error412ms262144 KiB
8Runtime error409ms262144 KiB
9Accepted1ms316 KiB
10Runtime error532ms262144 KiB
11Runtime error402ms262144 KiB
12Runtime error514ms262144 KiB
subtask30/25
13Accepted1ms500 KiB
14Accepted1ms316 KiB
15Accepted1ms316 KiB
16Accepted1ms508 KiB
17Accepted1ms316 KiB
18Accepted1ms352 KiB
19Accepted1ms316 KiB
20Accepted1ms396 KiB
21Accepted1ms316 KiB
22Accepted4ms332 KiB
23Accepted2ms520 KiB
24Accepted4ms384 KiB
25Accepted2ms316 KiB
26Accepted3ms568 KiB
27Accepted4ms564 KiB
28Accepted28ms1696 KiB
29Accepted6ms564 KiB
30Accepted30ms1820 KiB
31Runtime error460ms262144 KiB
32Accepted37ms2356 KiB
33Accepted12ms2100 KiB
subtask40/20
34Accepted1ms316 KiB
35Wrong answer1ms508 KiB
36Accepted1ms316 KiB
37Wrong answer1ms316 KiB
38Wrong answer1ms500 KiB
39Accepted1ms332 KiB
40Runtime error397ms262144 KiB
41Runtime error402ms262144 KiB
42Accepted1ms316 KiB
43Accepted1ms316 KiB
44Wrong answer1ms324 KiB
45Runtime error513ms262144 KiB
46Wrong answer1ms316 KiB
47Wrong answer1ms316 KiB
48Accepted1ms316 KiB
49Runtime error509ms262144 KiB
50Accepted1ms316 KiB
51Accepted1ms316 KiB
52Accepted1ms316 KiB
53Runtime error398ms262144 KiB
54Accepted1ms316 KiB
55Accepted1ms316 KiB
56Accepted1ms316 KiB
57Accepted1ms316 KiB
58Accepted1ms316 KiB
59Accepted1ms316 KiB
60Accepted1ms316 KiB
61Accepted1ms316 KiB
62Runtime error500ms262144 KiB
63Accepted1ms316 KiB
64Accepted1ms316 KiB
65Accepted1ms316 KiB
66Accepted1ms316 KiB
subtask50/15
67Accepted1ms316 KiB
68Accepted1ms316 KiB
69Accepted1ms316 KiB
70Runtime error412ms262144 KiB
71Runtime error521ms262144 KiB
72Runtime error518ms262144 KiB
73Runtime error412ms262144 KiB
74Runtime error409ms262144 KiB
75Accepted1ms316 KiB
76Runtime error532ms262144 KiB
77Runtime error402ms262144 KiB
78Runtime error514ms262144 KiB
79Accepted1ms500 KiB
80Accepted1ms316 KiB
81Accepted1ms316 KiB
82Accepted1ms508 KiB
83Accepted1ms316 KiB
84Accepted1ms352 KiB
85Accepted1ms316 KiB
86Accepted1ms396 KiB
87Accepted1ms316 KiB
88Accepted4ms332 KiB
89Accepted2ms520 KiB
90Accepted4ms384 KiB
91Accepted2ms316 KiB
92Accepted3ms568 KiB
93Accepted4ms564 KiB
94Accepted28ms1696 KiB
95Accepted6ms564 KiB
96Accepted30ms1820 KiB
97Runtime error460ms262144 KiB
98Accepted37ms2356 KiB
99Accepted12ms2100 KiB
100Wrong answer1ms508 KiB
101Accepted1ms316 KiB
102Wrong answer1ms316 KiB
103Wrong answer1ms500 KiB
104Accepted1ms332 KiB
105Runtime error397ms262144 KiB
106Runtime error402ms262144 KiB
107Accepted1ms316 KiB
108Accepted1ms316 KiB
109Wrong answer1ms324 KiB
110Runtime error513ms262144 KiB
111Wrong answer1ms316 KiB
112Wrong answer1ms316 KiB
113Accepted1ms316 KiB
114Runtime error509ms262144 KiB
115Accepted1ms316 KiB
116Accepted1ms316 KiB
117Accepted1ms316 KiB
118Runtime error398ms262144 KiB
119Accepted1ms316 KiB
120Accepted1ms316 KiB
121Accepted1ms316 KiB
122Accepted1ms316 KiB
123Accepted1ms316 KiB
124Accepted1ms316 KiB
125Accepted1ms316 KiB
126Accepted1ms316 KiB
127Runtime error500ms262144 KiB
128Accepted1ms316 KiB
129Accepted1ms316 KiB
130Accepted1ms316 KiB
131Accepted1ms316 KiB
132Runtime error518ms262144 KiB
133Accepted2ms564 KiB
134Runtime error412ms262144 KiB
135Runtime error510ms262144 KiB
136Runtime error405ms262144 KiB
137Runtime error398ms262144 KiB
138Runtime error509ms262144 KiB
139Accepted3ms564 KiB
140Runtime error407ms262144 KiB
141Runtime error509ms262144 KiB
142Runtime error412ms262144 KiB
143Accepted12ms1336 KiB
144Runtime error510ms262144 KiB
145Runtime error405ms262144 KiB
146Runtime error527ms262144 KiB
147Accepted18ms2356 KiB
148Accepted17ms1844 KiB
149Accepted12ms1272 KiB