248562026-02-16 03:07:21999Városnézéscpp17Wrong answer 20/8034ms2108 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);
    vector<int> lat(n),fok(n),fr(n,-1);
    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);
        fok[b]++;
    }
    vector<int> dp(n,LLONG_MIN),vis(n);
    queue<int> q;
    dp[0]=lat[0];
    vis[0]=1;
    q.push(0);
    for(int i = 1;i<n;i++){
        if(fok[i]==0){
            vis[i]=1;
            q.push(i);
        }
    }
    while(!q.empty()){
        int a=q.front();
        q.pop();
        for(int i : v[a]){
            if(dp[i]<dp[a]+lat[i]){
                dp[i]=dp[a]+lat[i];
                fr[i]=a;
            }
            fok[i]--;
            if(fok[i]==0&&vis[i]==0){
                vis[i]=1;
                q.push(i);
            }
        }
    }
    //for(int i : dp)cout<<i<<' ';return 0;
    if(vis[n-1]==0){
        cout<<-1;
        return 0;
    }
    cout<<dp[n-1]<<endl;
    int i = n-1;
    vector<int> ans;
    while(i!=-1){
        ans.push_back(i+1);
        i=fr[i];
    }
    reverse(ans.begin(),ans.end());
    for(int i : ans)cout<<i<<' ';
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
subtask220/20
2Accepted1ms500 KiB
3Accepted1ms316 KiB
4Accepted1ms500 KiB
5Accepted6ms564 KiB
6Accepted3ms564 KiB
7Accepted8ms1076 KiB
8Accepted8ms1128 KiB
9Accepted1ms316 KiB
10Accepted14ms1592 KiB
11Accepted1ms316 KiB
12Accepted1ms316 KiB
subtask30/25
13Accepted1ms316 KiB
14Accepted1ms316 KiB
15Accepted1ms316 KiB
16Accepted1ms316 KiB
17Accepted1ms316 KiB
18Accepted1ms316 KiB
19Accepted1ms316 KiB
20Wrong answer1ms508 KiB
21Wrong answer1ms316 KiB
22Accepted3ms316 KiB
23Wrong answer2ms492 KiB
24Accepted3ms316 KiB
25Accepted2ms316 KiB
26Wrong answer3ms456 KiB
27Wrong answer4ms564 KiB
28Accepted26ms1176 KiB
29Accepted4ms680 KiB
30Accepted28ms1296 KiB
31Wrong answer16ms924 KiB
32Wrong answer34ms1368 KiB
33Wrong answer10ms1564 KiB
subtask40/20
34Accepted1ms316 KiB
35Accepted1ms316 KiB
36Accepted1ms500 KiB
37Accepted1ms316 KiB
38Accepted1ms508 KiB
39Accepted1ms316 KiB
40Accepted1ms316 KiB
41Wrong answer1ms316 KiB
42Wrong answer1ms316 KiB
43Wrong answer1ms316 KiB
44Accepted1ms376 KiB
45Wrong answer1ms316 KiB
46Accepted1ms316 KiB
47Accepted1ms404 KiB
48Wrong answer1ms316 KiB
49Wrong answer2ms316 KiB
50Accepted2ms560 KiB
51Accepted2ms316 KiB
52Accepted1ms316 KiB
53Accepted1ms316 KiB
54Accepted1ms316 KiB
55Accepted1ms332 KiB
56Accepted1ms316 KiB
57Accepted1ms316 KiB
58Accepted1ms316 KiB
59Accepted1ms316 KiB
60Accepted1ms316 KiB
61Accepted1ms316 KiB
62Accepted1ms316 KiB
63Accepted1ms316 KiB
64Accepted1ms560 KiB
65Accepted1ms316 KiB
66Accepted1ms548 KiB
subtask50/15
67Accepted1ms316 KiB
68Accepted1ms500 KiB
69Accepted1ms316 KiB
70Accepted1ms500 KiB
71Accepted6ms564 KiB
72Accepted3ms564 KiB
73Accepted8ms1076 KiB
74Accepted8ms1128 KiB
75Accepted1ms316 KiB
76Accepted14ms1592 KiB
77Accepted1ms316 KiB
78Accepted1ms316 KiB
79Accepted1ms316 KiB
80Accepted1ms316 KiB
81Accepted1ms316 KiB
82Accepted1ms316 KiB
83Accepted1ms316 KiB
84Accepted1ms316 KiB
85Accepted1ms316 KiB
86Wrong answer1ms508 KiB
87Wrong answer1ms316 KiB
88Accepted3ms316 KiB
89Wrong answer2ms492 KiB
90Accepted3ms316 KiB
91Accepted2ms316 KiB
92Wrong answer3ms456 KiB
93Wrong answer4ms564 KiB
94Accepted26ms1176 KiB
95Accepted4ms680 KiB
96Accepted28ms1296 KiB
97Wrong answer16ms924 KiB
98Wrong answer34ms1368 KiB
99Wrong answer10ms1564 KiB
100Accepted1ms316 KiB
101Accepted1ms500 KiB
102Accepted1ms316 KiB
103Accepted1ms508 KiB
104Accepted1ms316 KiB
105Accepted1ms316 KiB
106Wrong answer1ms316 KiB
107Wrong answer1ms316 KiB
108Wrong answer1ms316 KiB
109Accepted1ms376 KiB
110Wrong answer1ms316 KiB
111Accepted1ms316 KiB
112Accepted1ms404 KiB
113Wrong answer1ms316 KiB
114Wrong answer2ms316 KiB
115Accepted2ms560 KiB
116Accepted2ms316 KiB
117Accepted1ms316 KiB
118Accepted1ms316 KiB
119Accepted1ms316 KiB
120Accepted1ms332 KiB
121Accepted1ms316 KiB
122Accepted1ms316 KiB
123Accepted1ms316 KiB
124Accepted1ms316 KiB
125Accepted1ms316 KiB
126Accepted1ms316 KiB
127Accepted1ms316 KiB
128Accepted1ms316 KiB
129Accepted1ms560 KiB
130Accepted1ms316 KiB
131Accepted1ms548 KiB
132Accepted3ms424 KiB
133Wrong answer2ms316 KiB
134Accepted4ms316 KiB
135Accepted2ms316 KiB
136Accepted3ms508 KiB
137Wrong answer3ms316 KiB
138Accepted3ms316 KiB
139Wrong answer3ms508 KiB
140Accepted4ms672 KiB
141Accepted3ms684 KiB
142Accepted9ms908 KiB
143Accepted9ms1168 KiB
144Accepted12ms1332 KiB
145Accepted8ms1076 KiB
146Accepted23ms2108 KiB
147Accepted17ms1588 KiB
148Accepted16ms1336 KiB
149Accepted10ms820 KiB