200212025-12-31 09:04:38VargaVivienVárosnézéscpp17Accepted 80/8035ms2536 KiB
#include <iostream>
#include <vector>
#include <string>

using namespace std;


vector <vector<int>> terkep;
int varos_lista[20001];
vector<bool> visited(200001,false);
vector<int> reszeredmeny(200001,-100);
int szam[20001];
int n;
int dist =-1;
int hossz=0;
void latogatas(int varos, int *latvanyossag, int szint)
{
   // bool vege = false;
    //vector<int> maximum;
   // vector<int> temp;
    int maxi = -2;
   // int ch_v=0;
   // cout << "szam" << &szam << endl;
   // cout << "temp" << &temp << endl;
   visited[varos]=true;
    if(varos == n)
    {
     reszeredmeny[n]=latvanyossag[varos - 1];
     //varos_lista[szint]=varos;
     szam[n]=1;
     visited[varos]=false;
     return;
     }
     if (terkep[varos].size()==0)
     {
      reszeredmeny[varos]=-1;
      visited[varos]=false;
      return;
     }
      else{
            for(auto x : terkep[varos])
        {

        if( reszeredmeny[x]< -1&& !visited[x]){

        latogatas(x, latvanyossag,  szint+1);
           }

        if(reszeredmeny[x]>maxi && !visited[x])
        {

            maxi=reszeredmeny[x];
            if (maxi>=0){
            varos_lista[varos]=x;
            reszeredmeny[varos]=maxi+latvanyossag[varos - 1];
            szam[varos]=szam[x]+1;
            }
            else
            {
             maxi=-1;
             reszeredmeny[varos]=maxi;
            }
        }
        }
        visited[varos]=false;
        }

}

int main()
{
    int m;
    int x,y;
    cin >> n >> m;
    int numbers[n];
    for(int i=0; i<n; i++) cin >> numbers[i];


    terkep.resize(n+1);
    for(int i = 0; i < m; i++)
    {
        cin >> x >> y;
        terkep[x].push_back(y);

    }
    int db = 0;
latogatas(1, numbers, 0);
    if (reszeredmeny[1]>=0)
    {
        cout << reszeredmeny[1] << endl;
        //cout << szam.size()<< endl;
        cout << 1 << " ";
        int next=1;
        for (int j=1;j<szam[1]; j++)
        {
            cout << varos_lista[next] << " ";
            next=varos_lista[next];
        }
    }
    else
    {
        cout << -1 << endl;
    }
    return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms1076 KiB
subtask220/20
2Accepted2ms1076 KiB
3Accepted2ms1260 KiB
4Accepted2ms1272 KiB
5Accepted6ms1332 KiB
6Accepted4ms1332 KiB
7Accepted8ms1588 KiB
8Accepted9ms1600 KiB
9Accepted2ms1076 KiB
10Accepted14ms2536 KiB
11Accepted2ms1076 KiB
12Accepted2ms1076 KiB
subtask325/25
13Accepted2ms1076 KiB
14Accepted2ms1076 KiB
15Accepted1ms1076 KiB
16Accepted2ms1136 KiB
17Accepted2ms1076 KiB
18Accepted2ms1076 KiB
19Accepted2ms1076 KiB
20Accepted2ms1096 KiB
21Accepted2ms1076 KiB
22Accepted4ms1076 KiB
23Accepted3ms1076 KiB
24Accepted4ms1112 KiB
25Accepted3ms1076 KiB
26Accepted3ms1232 KiB
27Accepted4ms1472 KiB
28Accepted26ms1492 KiB
29Accepted6ms1332 KiB
30Accepted28ms1688 KiB
31Accepted17ms1564 KiB
32Accepted35ms1588 KiB
33Accepted10ms1780 KiB
subtask420/20
34Accepted2ms1076 KiB
35Accepted2ms1076 KiB
36Accepted2ms1076 KiB
37Accepted2ms1076 KiB
38Accepted2ms1076 KiB
39Accepted2ms1208 KiB
40Accepted2ms1124 KiB
41Accepted2ms1076 KiB
42Accepted2ms996 KiB
43Accepted2ms1076 KiB
44Accepted2ms1076 KiB
45Accepted1ms1076 KiB
46Accepted2ms1268 KiB
47Accepted2ms1076 KiB
48Accepted2ms1076 KiB
49Accepted2ms1268 KiB
50Accepted1ms1008 KiB
51Accepted2ms1268 KiB
52Accepted2ms1076 KiB
53Accepted2ms1076 KiB
54Accepted2ms1060 KiB
55Accepted2ms1076 KiB
56Accepted2ms1036 KiB
57Accepted1ms1160 KiB
58Accepted2ms1076 KiB
59Accepted2ms1160 KiB
60Accepted2ms1084 KiB
61Accepted2ms1268 KiB
62Accepted1ms1076 KiB
63Accepted1ms1056 KiB
64Accepted2ms1076 KiB
65Accepted2ms1076 KiB
66Accepted1ms1076 KiB
subtask515/15
67Accepted2ms1076 KiB
68Accepted2ms1076 KiB
69Accepted2ms1260 KiB
70Accepted2ms1272 KiB
71Accepted6ms1332 KiB
72Accepted4ms1332 KiB
73Accepted8ms1588 KiB
74Accepted9ms1600 KiB
75Accepted2ms1076 KiB
76Accepted14ms2536 KiB
77Accepted2ms1076 KiB
78Accepted2ms1076 KiB
79Accepted2ms1076 KiB
80Accepted2ms1076 KiB
81Accepted1ms1076 KiB
82Accepted2ms1136 KiB
83Accepted2ms1076 KiB
84Accepted2ms1076 KiB
85Accepted2ms1076 KiB
86Accepted2ms1096 KiB
87Accepted2ms1076 KiB
88Accepted4ms1076 KiB
89Accepted3ms1076 KiB
90Accepted4ms1112 KiB
91Accepted3ms1076 KiB
92Accepted3ms1232 KiB
93Accepted4ms1472 KiB
94Accepted26ms1492 KiB
95Accepted6ms1332 KiB
96Accepted28ms1688 KiB
97Accepted17ms1564 KiB
98Accepted35ms1588 KiB
99Accepted10ms1780 KiB
100Accepted2ms1076 KiB
101Accepted2ms1076 KiB
102Accepted2ms1076 KiB
103Accepted2ms1076 KiB
104Accepted2ms1208 KiB
105Accepted2ms1124 KiB
106Accepted2ms1076 KiB
107Accepted2ms996 KiB
108Accepted2ms1076 KiB
109Accepted2ms1076 KiB
110Accepted1ms1076 KiB
111Accepted2ms1268 KiB
112Accepted2ms1076 KiB
113Accepted2ms1076 KiB
114Accepted2ms1268 KiB
115Accepted1ms1008 KiB
116Accepted2ms1268 KiB
117Accepted2ms1076 KiB
118Accepted2ms1076 KiB
119Accepted2ms1060 KiB
120Accepted2ms1076 KiB
121Accepted2ms1036 KiB
122Accepted1ms1160 KiB
123Accepted2ms1076 KiB
124Accepted2ms1160 KiB
125Accepted2ms1084 KiB
126Accepted2ms1268 KiB
127Accepted1ms1076 KiB
128Accepted1ms1056 KiB
129Accepted2ms1076 KiB
130Accepted2ms1076 KiB
131Accepted1ms1076 KiB
132Accepted4ms1260 KiB
133Accepted3ms1092 KiB
134Accepted4ms1284 KiB
135Accepted3ms1260 KiB
136Accepted4ms1244 KiB
137Accepted3ms1076 KiB
138Accepted4ms1076 KiB
139Accepted4ms1224 KiB
140Accepted6ms1500 KiB
141Accepted3ms1316 KiB
142Accepted9ms1512 KiB
143Accepted10ms1776 KiB
144Accepted13ms1732 KiB
145Accepted8ms1740 KiB
146Accepted21ms2384 KiB
147Accepted18ms2300 KiB
148Accepted17ms1844 KiB
149Accepted12ms1704 KiB