248522026-02-16 02:44:12999Városnézéscpp17Runtime error 0/80508ms262144 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),fr(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),vis(n);
    queue<int> q;
    for(int i = 0;i<n;i++){
        if(fok[i]==0&&i!=n-1){
            vis[i]=1;
            q.push(i);
            dp[i]=-2;
        }
        else if(fok[i]==0&&i==n-1){
            vis[i]=1;
            dp[i]=lat[i];
            q.push(i);
        }
    }
    int cntt=0;
    while(!q.empty()){
        cntt++;
        if(cntt>n){
            cout<<-1;return 0;
        }
        int a=q.front();
        q.pop();
        if(dp[a]!=-2&&a!=n-1){
            for(int u:v[a]){
                if(dp[a]<dp[u]){
                    dp[a]=max(dp[a],dp[u]);
                    fr[a]=u;
                }
            }
            dp[a]+=lat[a];
        }
        for(int u : g[a]){
            fok[u]--;
            if(fok[u]==0&&vis[u]==0){
                vis[u]=1;
                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);
        i=fr[i];
    }
    ans.push_back(n);
    for(int i : ans)cout<<i<<' ';
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
subtask20/20
2Accepted1ms316 KiB
3Accepted1ms316 KiB
4Runtime error370ms262144 KiB
5Runtime error365ms262144 KiB
6Runtime error474ms262144 KiB
7Runtime error477ms262144 KiB
8Runtime error368ms262144 KiB
9Accepted1ms316 KiB
10Runtime error442ms262144 KiB
11Runtime error469ms262144 KiB
12Runtime error470ms262144 KiB
subtask30/25
13Accepted1ms316 KiB
14Accepted1ms316 KiB
15Accepted1ms316 KiB
16Accepted1ms508 KiB
17Accepted1ms316 KiB
18Accepted1ms316 KiB
19Accepted1ms508 KiB
20Accepted1ms508 KiB
21Accepted1ms316 KiB
22Accepted4ms316 KiB
23Accepted2ms564 KiB
24Accepted4ms572 KiB
25Accepted3ms316 KiB
26Accepted3ms564 KiB
27Accepted4ms564 KiB
28Accepted28ms1764 KiB
29Accepted6ms632 KiB
30Accepted32ms2016 KiB
31Runtime error372ms262144 KiB
32Accepted39ms2356 KiB
33Accepted12ms2356 KiB
subtask40/20
34Accepted1ms316 KiB
35Runtime error361ms262144 KiB
36Accepted1ms316 KiB
37Runtime error469ms262144 KiB
38Runtime error467ms262144 KiB
39Accepted1ms316 KiB
40Runtime error358ms262144 KiB
41Runtime error365ms262144 KiB
42Accepted1ms316 KiB
43Accepted1ms316 KiB
44Runtime error361ms262144 KiB
45Runtime error465ms262144 KiB
46Runtime error467ms262144 KiB
47Runtime error360ms262144 KiB
48Accepted1ms316 KiB
49Runtime error354ms262144 KiB
50Accepted1ms316 KiB
51Accepted1ms316 KiB
52Accepted1ms316 KiB
53Runtime error470ms262144 KiB
54Accepted1ms316 KiB
55Accepted1ms316 KiB
56Accepted1ms316 KiB
57Accepted1ms344 KiB
58Accepted1ms316 KiB
59Accepted1ms316 KiB
60Accepted1ms316 KiB
61Accepted1ms560 KiB
62Runtime error469ms262144 KiB
63Accepted1ms316 KiB
64Accepted1ms316 KiB
65Accepted1ms316 KiB
66Accepted1ms316 KiB
subtask50/15
67Accepted1ms316 KiB
68Accepted1ms316 KiB
69Accepted1ms316 KiB
70Runtime error370ms262144 KiB
71Runtime error365ms262144 KiB
72Runtime error474ms262144 KiB
73Runtime error477ms262144 KiB
74Runtime error368ms262144 KiB
75Accepted1ms316 KiB
76Runtime error442ms262144 KiB
77Runtime error469ms262144 KiB
78Runtime error470ms262144 KiB
79Accepted1ms316 KiB
80Accepted1ms316 KiB
81Accepted1ms316 KiB
82Accepted1ms508 KiB
83Accepted1ms316 KiB
84Accepted1ms316 KiB
85Accepted1ms508 KiB
86Accepted1ms508 KiB
87Accepted1ms316 KiB
88Accepted4ms316 KiB
89Accepted2ms564 KiB
90Accepted4ms572 KiB
91Accepted3ms316 KiB
92Accepted3ms564 KiB
93Accepted4ms564 KiB
94Accepted28ms1764 KiB
95Accepted6ms632 KiB
96Accepted32ms2016 KiB
97Runtime error372ms262144 KiB
98Accepted39ms2356 KiB
99Accepted12ms2356 KiB
100Runtime error361ms262144 KiB
101Accepted1ms316 KiB
102Runtime error469ms262144 KiB
103Runtime error467ms262144 KiB
104Accepted1ms316 KiB
105Runtime error358ms262144 KiB
106Runtime error365ms262144 KiB
107Accepted1ms316 KiB
108Accepted1ms316 KiB
109Runtime error361ms262144 KiB
110Runtime error465ms262144 KiB
111Runtime error467ms262144 KiB
112Runtime error360ms262144 KiB
113Accepted1ms316 KiB
114Runtime error354ms262144 KiB
115Accepted1ms316 KiB
116Accepted1ms316 KiB
117Accepted1ms316 KiB
118Runtime error470ms262144 KiB
119Accepted1ms316 KiB
120Accepted1ms316 KiB
121Accepted1ms316 KiB
122Accepted1ms344 KiB
123Accepted1ms316 KiB
124Accepted1ms316 KiB
125Accepted1ms316 KiB
126Accepted1ms560 KiB
127Runtime error469ms262144 KiB
128Accepted1ms316 KiB
129Accepted1ms316 KiB
130Accepted1ms316 KiB
131Accepted1ms316 KiB
132Runtime error469ms262144 KiB
133Accepted3ms564 KiB
134Runtime error365ms262144 KiB
135Runtime error469ms262144 KiB
136Runtime error356ms262144 KiB
137Runtime error361ms262144 KiB
138Runtime error367ms262144 KiB
139Accepted4ms564 KiB
140Runtime error474ms262144 KiB
141Runtime error474ms262144 KiB
142Runtime error479ms262144 KiB
143Accepted12ms1596 KiB
144Runtime error363ms262144 KiB
145Runtime error508ms262144 KiB
146Runtime error388ms262144 KiB
147Accepted19ms2612 KiB
148Accepted18ms1844 KiB
149Accepted13ms1076 KiB