229582026-01-16 09:39:05Leventusz09Városnézéscpp17Runtime error 40/80707ms262144 KiB
#include <iostream>
#include <vector>
#include <stdint.h>

using namespace std;

struct Ter {
    vector<int32_t> et;
    //vector<int32_t> ef;
    int32_t n;  // látványosságok száma
    int32_t an = -1; // sok látványosság
    int32_t ob = -1; // előző elem
};


int main(){
    Ter terek[20'000];
    int32_t N, M;
    cin >> N >> M;

    for(int32_t i=0; i<N; i++) cin >> terek[i].n;

    for(int32_t i=0; i<M; i++){
        int32_t t1, t2;
        cin >> t1 >> t2;
        terek[t1-1].et.push_back(t2-1);
        //terek[t2-1].ef.push_back(t1-1);
    }

    terek[0].an = terek[0].n;
    vector<int32_t> q;
    q.push_back(0);
    int32_t si= 0;
    while(si < q.size()){
        for(int32_t&x:terek[q[si]].et){
            q.push_back(x);
            if(terek[x].an < terek[q[si]].an + terek[x].n) {
                terek[x].an = terek[q[si]].an + terek[x].n;
                terek[x].ob = q[si];
            }
        }
        si++;
    }

    vector<int32_t> o1;
    for(int32_t i=N - 1; i != 0; i = terek[i].ob){
        o1.push_back(i+1);
        if(i == -1){
            cout << -1 << endl;
            return 0;
        }
    }
    cout << terek[N - 1].an << endl;
    cout << 1 << " ";
    for(int32_t i = o1.size()-1; i >= 0; i--) cout << o1[i] << " "; 
    cout << endl;

    return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms1076 KiB
subtask220/20
2Accepted1ms1076 KiB
3Accepted2ms1180 KiB
4Accepted2ms1180 KiB
5Accepted4ms1176 KiB
6Accepted3ms1076 KiB
7Accepted8ms1432 KiB
8Accepted8ms1340 KiB
9Accepted2ms1080 KiB
10Accepted14ms1588 KiB
11Accepted1ms1076 KiB
12Accepted2ms1076 KiB
subtask30/25
13Accepted2ms1268 KiB
14Accepted1ms1076 KiB
15Accepted1ms1260 KiB
16Accepted2ms1648 KiB
17Accepted2ms1076 KiB
18Accepted2ms1076 KiB
19Accepted1ms1076 KiB
20Accepted1ms1076 KiB
21Accepted2ms1076 KiB
22Runtime error552ms262144 KiB
23Accepted2ms1076 KiB
24Runtime error449ms262144 KiB
25Accepted27ms9360 KiB
26Accepted3ms1076 KiB
27Accepted4ms1076 KiB
28Runtime error606ms262144 KiB
29Accepted13ms5388 KiB
30Runtime error490ms262144 KiB
31Accepted16ms1204 KiB
32Accepted34ms1348 KiB
33Accepted10ms1076 KiB
subtask420/20
34Accepted2ms1076 KiB
35Accepted2ms1076 KiB
36Accepted2ms1076 KiB
37Accepted2ms1076 KiB
38Accepted2ms1452 KiB
39Accepted2ms1148 KiB
40Accepted2ms1076 KiB
41Accepted2ms1076 KiB
42Accepted2ms1268 KiB
43Accepted2ms1076 KiB
44Accepted3ms1456 KiB
45Accepted2ms1076 KiB
46Accepted8ms3256 KiB
47Accepted2ms1268 KiB
48Accepted2ms1076 KiB
49Accepted2ms1076 KiB
50Accepted2ms1076 KiB
51Accepted2ms1076 KiB
52Accepted1ms1076 KiB
53Accepted2ms1076 KiB
54Accepted2ms1076 KiB
55Accepted2ms1076 KiB
56Accepted2ms1116 KiB
57Accepted1ms1076 KiB
58Accepted1ms1076 KiB
59Accepted2ms1108 KiB
60Accepted2ms1076 KiB
61Accepted2ms1232 KiB
62Accepted2ms1076 KiB
63Accepted1ms1080 KiB
64Accepted2ms1076 KiB
65Accepted1ms1076 KiB
66Accepted1ms1136 KiB
subtask50/15
67Accepted2ms1076 KiB
68Accepted1ms1076 KiB
69Accepted2ms1180 KiB
70Accepted2ms1180 KiB
71Accepted4ms1176 KiB
72Accepted3ms1076 KiB
73Accepted8ms1432 KiB
74Accepted8ms1340 KiB
75Accepted2ms1080 KiB
76Accepted14ms1588 KiB
77Accepted1ms1076 KiB
78Accepted2ms1076 KiB
79Accepted2ms1268 KiB
80Accepted1ms1076 KiB
81Accepted1ms1260 KiB
82Accepted2ms1648 KiB
83Accepted2ms1076 KiB
84Accepted2ms1076 KiB
85Accepted1ms1076 KiB
86Accepted1ms1076 KiB
87Accepted2ms1076 KiB
88Runtime error552ms262144 KiB
89Accepted2ms1076 KiB
90Runtime error449ms262144 KiB
91Accepted27ms9360 KiB
92Accepted3ms1076 KiB
93Accepted4ms1076 KiB
94Runtime error606ms262144 KiB
95Accepted13ms5388 KiB
96Runtime error490ms262144 KiB
97Accepted16ms1204 KiB
98Accepted34ms1348 KiB
99Accepted10ms1076 KiB
100Accepted2ms1076 KiB
101Accepted2ms1076 KiB
102Accepted2ms1076 KiB
103Accepted2ms1452 KiB
104Accepted2ms1148 KiB
105Accepted2ms1076 KiB
106Accepted2ms1076 KiB
107Accepted2ms1268 KiB
108Accepted2ms1076 KiB
109Accepted3ms1456 KiB
110Accepted2ms1076 KiB
111Accepted8ms3256 KiB
112Accepted2ms1268 KiB
113Accepted2ms1076 KiB
114Accepted2ms1076 KiB
115Accepted2ms1076 KiB
116Accepted2ms1076 KiB
117Accepted1ms1076 KiB
118Accepted2ms1076 KiB
119Accepted2ms1076 KiB
120Accepted2ms1076 KiB
121Accepted2ms1116 KiB
122Accepted1ms1076 KiB
123Accepted1ms1076 KiB
124Accepted2ms1108 KiB
125Accepted2ms1076 KiB
126Accepted2ms1232 KiB
127Accepted2ms1076 KiB
128Accepted1ms1080 KiB
129Accepted2ms1076 KiB
130Accepted1ms1076 KiB
131Accepted1ms1136 KiB
132Runtime error555ms262144 KiB
133Accepted2ms1372 KiB
134Runtime error575ms262144 KiB
135Accepted391ms132636 KiB
136Runtime error462ms262144 KiB
137Accepted6ms2216 KiB
138Runtime error423ms262144 KiB
139Accepted4ms1076 KiB
140Accepted6ms1332 KiB
141Accepted3ms1076 KiB
142Accepted8ms1332 KiB
143Accepted14ms2528 KiB
144Accepted10ms1588 KiB
145Accepted8ms1588 KiB
146Accepted20ms2100 KiB
147Runtime error606ms262144 KiB
148Runtime error707ms262144 KiB
149Runtime error639ms262144 KiB