200212025-12-31 09:04:38VargaVivienVárosnézéscpp17Elfogadva 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms1076 KiB
subtask220/20
2Elfogadva2ms1076 KiB
3Elfogadva2ms1260 KiB
4Elfogadva2ms1272 KiB
5Elfogadva6ms1332 KiB
6Elfogadva4ms1332 KiB
7Elfogadva8ms1588 KiB
8Elfogadva9ms1600 KiB
9Elfogadva2ms1076 KiB
10Elfogadva14ms2536 KiB
11Elfogadva2ms1076 KiB
12Elfogadva2ms1076 KiB
subtask325/25
13Elfogadva2ms1076 KiB
14Elfogadva2ms1076 KiB
15Elfogadva1ms1076 KiB
16Elfogadva2ms1136 KiB
17Elfogadva2ms1076 KiB
18Elfogadva2ms1076 KiB
19Elfogadva2ms1076 KiB
20Elfogadva2ms1096 KiB
21Elfogadva2ms1076 KiB
22Elfogadva4ms1076 KiB
23Elfogadva3ms1076 KiB
24Elfogadva4ms1112 KiB
25Elfogadva3ms1076 KiB
26Elfogadva3ms1232 KiB
27Elfogadva4ms1472 KiB
28Elfogadva26ms1492 KiB
29Elfogadva6ms1332 KiB
30Elfogadva28ms1688 KiB
31Elfogadva17ms1564 KiB
32Elfogadva35ms1588 KiB
33Elfogadva10ms1780 KiB
subtask420/20
34Elfogadva2ms1076 KiB
35Elfogadva2ms1076 KiB
36Elfogadva2ms1076 KiB
37Elfogadva2ms1076 KiB
38Elfogadva2ms1076 KiB
39Elfogadva2ms1208 KiB
40Elfogadva2ms1124 KiB
41Elfogadva2ms1076 KiB
42Elfogadva2ms996 KiB
43Elfogadva2ms1076 KiB
44Elfogadva2ms1076 KiB
45Elfogadva1ms1076 KiB
46Elfogadva2ms1268 KiB
47Elfogadva2ms1076 KiB
48Elfogadva2ms1076 KiB
49Elfogadva2ms1268 KiB
50Elfogadva1ms1008 KiB
51Elfogadva2ms1268 KiB
52Elfogadva2ms1076 KiB
53Elfogadva2ms1076 KiB
54Elfogadva2ms1060 KiB
55Elfogadva2ms1076 KiB
56Elfogadva2ms1036 KiB
57Elfogadva1ms1160 KiB
58Elfogadva2ms1076 KiB
59Elfogadva2ms1160 KiB
60Elfogadva2ms1084 KiB
61Elfogadva2ms1268 KiB
62Elfogadva1ms1076 KiB
63Elfogadva1ms1056 KiB
64Elfogadva2ms1076 KiB
65Elfogadva2ms1076 KiB
66Elfogadva1ms1076 KiB
subtask515/15
67Elfogadva2ms1076 KiB
68Elfogadva2ms1076 KiB
69Elfogadva2ms1260 KiB
70Elfogadva2ms1272 KiB
71Elfogadva6ms1332 KiB
72Elfogadva4ms1332 KiB
73Elfogadva8ms1588 KiB
74Elfogadva9ms1600 KiB
75Elfogadva2ms1076 KiB
76Elfogadva14ms2536 KiB
77Elfogadva2ms1076 KiB
78Elfogadva2ms1076 KiB
79Elfogadva2ms1076 KiB
80Elfogadva2ms1076 KiB
81Elfogadva1ms1076 KiB
82Elfogadva2ms1136 KiB
83Elfogadva2ms1076 KiB
84Elfogadva2ms1076 KiB
85Elfogadva2ms1076 KiB
86Elfogadva2ms1096 KiB
87Elfogadva2ms1076 KiB
88Elfogadva4ms1076 KiB
89Elfogadva3ms1076 KiB
90Elfogadva4ms1112 KiB
91Elfogadva3ms1076 KiB
92Elfogadva3ms1232 KiB
93Elfogadva4ms1472 KiB
94Elfogadva26ms1492 KiB
95Elfogadva6ms1332 KiB
96Elfogadva28ms1688 KiB
97Elfogadva17ms1564 KiB
98Elfogadva35ms1588 KiB
99Elfogadva10ms1780 KiB
100Elfogadva2ms1076 KiB
101Elfogadva2ms1076 KiB
102Elfogadva2ms1076 KiB
103Elfogadva2ms1076 KiB
104Elfogadva2ms1208 KiB
105Elfogadva2ms1124 KiB
106Elfogadva2ms1076 KiB
107Elfogadva2ms996 KiB
108Elfogadva2ms1076 KiB
109Elfogadva2ms1076 KiB
110Elfogadva1ms1076 KiB
111Elfogadva2ms1268 KiB
112Elfogadva2ms1076 KiB
113Elfogadva2ms1076 KiB
114Elfogadva2ms1268 KiB
115Elfogadva1ms1008 KiB
116Elfogadva2ms1268 KiB
117Elfogadva2ms1076 KiB
118Elfogadva2ms1076 KiB
119Elfogadva2ms1060 KiB
120Elfogadva2ms1076 KiB
121Elfogadva2ms1036 KiB
122Elfogadva1ms1160 KiB
123Elfogadva2ms1076 KiB
124Elfogadva2ms1160 KiB
125Elfogadva2ms1084 KiB
126Elfogadva2ms1268 KiB
127Elfogadva1ms1076 KiB
128Elfogadva1ms1056 KiB
129Elfogadva2ms1076 KiB
130Elfogadva2ms1076 KiB
131Elfogadva1ms1076 KiB
132Elfogadva4ms1260 KiB
133Elfogadva3ms1092 KiB
134Elfogadva4ms1284 KiB
135Elfogadva3ms1260 KiB
136Elfogadva4ms1244 KiB
137Elfogadva3ms1076 KiB
138Elfogadva4ms1076 KiB
139Elfogadva4ms1224 KiB
140Elfogadva6ms1500 KiB
141Elfogadva3ms1316 KiB
142Elfogadva9ms1512 KiB
143Elfogadva10ms1776 KiB
144Elfogadva13ms1732 KiB
145Elfogadva8ms1740 KiB
146Elfogadva21ms2384 KiB
147Elfogadva18ms2300 KiB
148Elfogadva17ms1844 KiB
149Elfogadva12ms1704 KiB