197102025-12-19 16:35:13szabelrVárosnézéscpp17Elfogadva 80/8013ms2024 KiB
// Városnézés.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <vector>
using namespace std;
void dfs(vector<int>& megold, vector<vector<int>>& graph, vector<int> &merre, int latv[20001],int n,int v)
{
    if (v == n)
    {
        megold[v] = latv[v];
        return;
    }
    if (graph[v].size() == 0)
    {
        megold[v] = -1;
        return ;
    }
    
    else
    {
        int maxi=-1;
        int melyik = -1;
        for (int i = 0; i < graph[v].size(); i++)
        {
            
            int szomszed=graph[v][i];
            if(megold[szomszed]==-2)
                dfs(megold, graph, merre, latv, n, szomszed);
            if (megold[szomszed] > maxi)
            {
                maxi = megold[szomszed];
                melyik = szomszed;
            }
        }
        if (maxi != -1)
        {
            megold[v] = maxi + latv[v];
            merre[v] = melyik;
        }
        else
            megold[v] = -1;
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m,x,y;
    cin >> n >> m;
    int latv[20001];
    vector<int> megold(20001, -2);
    vector<int> merre(20001, -1);
    for (int i = 1; i <= n; i++)
    {
        cin >> x;
        latv[i] = x;
    }
    vector<vector<int>> graph(n+1);
    for (int i = 1; i <= m; i++)
    {
        cin >> x >> y;
        graph[x].push_back(y);
    }
    dfs(megold,graph,merre,latv,n,1);
    if (megold[1] == -1)
        cout << -1;
    else
    {
        cout << megold[1]<<endl;
        cout << 1 << " ";
        int v = 1;
        while (v != n)
        {
            v = merre[v];
            cout << v << " ";
        }
    }
    
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms564 KiB
subtask220/20
2Elfogadva1ms564 KiB
3Elfogadva1ms564 KiB
4Elfogadva1ms564 KiB
5Elfogadva3ms568 KiB
6Elfogadva2ms568 KiB
7Elfogadva4ms868 KiB
8Elfogadva4ms868 KiB
9Elfogadva1ms564 KiB
10Elfogadva8ms2024 KiB
11Elfogadva1ms564 KiB
12Elfogadva1ms564 KiB
subtask325/25
13Elfogadva1ms564 KiB
14Elfogadva1ms564 KiB
15Elfogadva1ms564 KiB
16Elfogadva1ms564 KiB
17Elfogadva1ms564 KiB
18Elfogadva1ms348 KiB
19Elfogadva1ms564 KiB
20Elfogadva1ms564 KiB
21Elfogadva2ms760 KiB
22Elfogadva3ms636 KiB
23Elfogadva2ms564 KiB
24Elfogadva2ms564 KiB
25Elfogadva1ms564 KiB
26Elfogadva2ms564 KiB
27Elfogadva2ms564 KiB
28Elfogadva9ms864 KiB
29Elfogadva3ms580 KiB
30Elfogadva10ms1076 KiB
31Elfogadva7ms820 KiB
32Elfogadva13ms1068 KiB
33Elfogadva4ms1076 KiB
subtask420/20
34Elfogadva1ms564 KiB
35Elfogadva2ms564 KiB
36Elfogadva2ms564 KiB
37Elfogadva1ms564 KiB
38Elfogadva1ms564 KiB
39Elfogadva1ms800 KiB
40Elfogadva1ms492 KiB
41Elfogadva1ms564 KiB
42Elfogadva1ms564 KiB
43Elfogadva1ms564 KiB
44Elfogadva1ms568 KiB
45Elfogadva2ms564 KiB
46Elfogadva1ms340 KiB
47Elfogadva1ms564 KiB
48Elfogadva1ms564 KiB
49Elfogadva1ms564 KiB
50Elfogadva1ms564 KiB
51Elfogadva1ms564 KiB
52Elfogadva1ms564 KiB
53Elfogadva1ms564 KiB
54Elfogadva1ms564 KiB
55Elfogadva1ms756 KiB
56Elfogadva1ms408 KiB
57Elfogadva1ms568 KiB
58Elfogadva2ms564 KiB
59Elfogadva2ms564 KiB
60Elfogadva1ms564 KiB
61Elfogadva1ms332 KiB
62Elfogadva1ms564 KiB
63Elfogadva1ms564 KiB
64Elfogadva1ms556 KiB
65Elfogadva1ms508 KiB
66Elfogadva1ms756 KiB
subtask515/15
67Elfogadva1ms564 KiB
68Elfogadva1ms564 KiB
69Elfogadva1ms564 KiB
70Elfogadva1ms564 KiB
71Elfogadva3ms568 KiB
72Elfogadva2ms568 KiB
73Elfogadva4ms868 KiB
74Elfogadva4ms868 KiB
75Elfogadva1ms564 KiB
76Elfogadva8ms2024 KiB
77Elfogadva1ms564 KiB
78Elfogadva1ms564 KiB
79Elfogadva1ms564 KiB
80Elfogadva1ms564 KiB
81Elfogadva1ms564 KiB
82Elfogadva1ms564 KiB
83Elfogadva1ms564 KiB
84Elfogadva1ms348 KiB
85Elfogadva1ms564 KiB
86Elfogadva1ms564 KiB
87Elfogadva2ms760 KiB
88Elfogadva3ms636 KiB
89Elfogadva2ms564 KiB
90Elfogadva2ms564 KiB
91Elfogadva1ms564 KiB
92Elfogadva2ms564 KiB
93Elfogadva2ms564 KiB
94Elfogadva9ms864 KiB
95Elfogadva3ms580 KiB
96Elfogadva10ms1076 KiB
97Elfogadva7ms820 KiB
98Elfogadva13ms1068 KiB
99Elfogadva4ms1076 KiB
100Elfogadva2ms564 KiB
101Elfogadva2ms564 KiB
102Elfogadva1ms564 KiB
103Elfogadva1ms564 KiB
104Elfogadva1ms800 KiB
105Elfogadva1ms492 KiB
106Elfogadva1ms564 KiB
107Elfogadva1ms564 KiB
108Elfogadva1ms564 KiB
109Elfogadva1ms568 KiB
110Elfogadva2ms564 KiB
111Elfogadva1ms340 KiB
112Elfogadva1ms564 KiB
113Elfogadva1ms564 KiB
114Elfogadva1ms564 KiB
115Elfogadva1ms564 KiB
116Elfogadva1ms564 KiB
117Elfogadva1ms564 KiB
118Elfogadva1ms564 KiB
119Elfogadva1ms564 KiB
120Elfogadva1ms756 KiB
121Elfogadva1ms408 KiB
122Elfogadva1ms568 KiB
123Elfogadva2ms564 KiB
124Elfogadva2ms564 KiB
125Elfogadva1ms564 KiB
126Elfogadva1ms332 KiB
127Elfogadva1ms564 KiB
128Elfogadva1ms564 KiB
129Elfogadva1ms556 KiB
130Elfogadva1ms508 KiB
131Elfogadva1ms756 KiB
132Elfogadva2ms760 KiB
133Elfogadva2ms564 KiB
134Elfogadva3ms564 KiB
135Elfogadva2ms800 KiB
136Elfogadva2ms568 KiB
137Elfogadva2ms564 KiB
138Elfogadva3ms564 KiB
139Elfogadva2ms564 KiB
140Elfogadva3ms564 KiB
141Elfogadva2ms564 KiB
142Elfogadva4ms820 KiB
143Elfogadva4ms1076 KiB
144Elfogadva6ms1212 KiB
145Elfogadva4ms1068 KiB
146Elfogadva9ms1628 KiB
147Elfogadva8ms1364 KiB
148Elfogadva7ms1092 KiB
149Elfogadva4ms1268 KiB