197102025-12-19 16:35:13szabelrVárosnézéscpp17Accepted 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
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms564 KiB
subtask220/20
2Accepted1ms564 KiB
3Accepted1ms564 KiB
4Accepted1ms564 KiB
5Accepted3ms568 KiB
6Accepted2ms568 KiB
7Accepted4ms868 KiB
8Accepted4ms868 KiB
9Accepted1ms564 KiB
10Accepted8ms2024 KiB
11Accepted1ms564 KiB
12Accepted1ms564 KiB
subtask325/25
13Accepted1ms564 KiB
14Accepted1ms564 KiB
15Accepted1ms564 KiB
16Accepted1ms564 KiB
17Accepted1ms564 KiB
18Accepted1ms348 KiB
19Accepted1ms564 KiB
20Accepted1ms564 KiB
21Accepted2ms760 KiB
22Accepted3ms636 KiB
23Accepted2ms564 KiB
24Accepted2ms564 KiB
25Accepted1ms564 KiB
26Accepted2ms564 KiB
27Accepted2ms564 KiB
28Accepted9ms864 KiB
29Accepted3ms580 KiB
30Accepted10ms1076 KiB
31Accepted7ms820 KiB
32Accepted13ms1068 KiB
33Accepted4ms1076 KiB
subtask420/20
34Accepted1ms564 KiB
35Accepted2ms564 KiB
36Accepted2ms564 KiB
37Accepted1ms564 KiB
38Accepted1ms564 KiB
39Accepted1ms800 KiB
40Accepted1ms492 KiB
41Accepted1ms564 KiB
42Accepted1ms564 KiB
43Accepted1ms564 KiB
44Accepted1ms568 KiB
45Accepted2ms564 KiB
46Accepted1ms340 KiB
47Accepted1ms564 KiB
48Accepted1ms564 KiB
49Accepted1ms564 KiB
50Accepted1ms564 KiB
51Accepted1ms564 KiB
52Accepted1ms564 KiB
53Accepted1ms564 KiB
54Accepted1ms564 KiB
55Accepted1ms756 KiB
56Accepted1ms408 KiB
57Accepted1ms568 KiB
58Accepted2ms564 KiB
59Accepted2ms564 KiB
60Accepted1ms564 KiB
61Accepted1ms332 KiB
62Accepted1ms564 KiB
63Accepted1ms564 KiB
64Accepted1ms556 KiB
65Accepted1ms508 KiB
66Accepted1ms756 KiB
subtask515/15
67Accepted1ms564 KiB
68Accepted1ms564 KiB
69Accepted1ms564 KiB
70Accepted1ms564 KiB
71Accepted3ms568 KiB
72Accepted2ms568 KiB
73Accepted4ms868 KiB
74Accepted4ms868 KiB
75Accepted1ms564 KiB
76Accepted8ms2024 KiB
77Accepted1ms564 KiB
78Accepted1ms564 KiB
79Accepted1ms564 KiB
80Accepted1ms564 KiB
81Accepted1ms564 KiB
82Accepted1ms564 KiB
83Accepted1ms564 KiB
84Accepted1ms348 KiB
85Accepted1ms564 KiB
86Accepted1ms564 KiB
87Accepted2ms760 KiB
88Accepted3ms636 KiB
89Accepted2ms564 KiB
90Accepted2ms564 KiB
91Accepted1ms564 KiB
92Accepted2ms564 KiB
93Accepted2ms564 KiB
94Accepted9ms864 KiB
95Accepted3ms580 KiB
96Accepted10ms1076 KiB
97Accepted7ms820 KiB
98Accepted13ms1068 KiB
99Accepted4ms1076 KiB
100Accepted2ms564 KiB
101Accepted2ms564 KiB
102Accepted1ms564 KiB
103Accepted1ms564 KiB
104Accepted1ms800 KiB
105Accepted1ms492 KiB
106Accepted1ms564 KiB
107Accepted1ms564 KiB
108Accepted1ms564 KiB
109Accepted1ms568 KiB
110Accepted2ms564 KiB
111Accepted1ms340 KiB
112Accepted1ms564 KiB
113Accepted1ms564 KiB
114Accepted1ms564 KiB
115Accepted1ms564 KiB
116Accepted1ms564 KiB
117Accepted1ms564 KiB
118Accepted1ms564 KiB
119Accepted1ms564 KiB
120Accepted1ms756 KiB
121Accepted1ms408 KiB
122Accepted1ms568 KiB
123Accepted2ms564 KiB
124Accepted2ms564 KiB
125Accepted1ms564 KiB
126Accepted1ms332 KiB
127Accepted1ms564 KiB
128Accepted1ms564 KiB
129Accepted1ms556 KiB
130Accepted1ms508 KiB
131Accepted1ms756 KiB
132Accepted2ms760 KiB
133Accepted2ms564 KiB
134Accepted3ms564 KiB
135Accepted2ms800 KiB
136Accepted2ms568 KiB
137Accepted2ms564 KiB
138Accepted3ms564 KiB
139Accepted2ms564 KiB
140Accepted3ms564 KiB
141Accepted2ms564 KiB
142Accepted4ms820 KiB
143Accepted4ms1076 KiB
144Accepted6ms1212 KiB
145Accepted4ms1068 KiB
146Accepted9ms1628 KiB
147Accepted8ms1364 KiB
148Accepted7ms1092 KiB
149Accepted4ms1268 KiB