195822025-12-16 09:50:44szabel26Városnézéscpp17Hibás válasz 25/8035ms1648 KiB
// varosnezes.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <vector>
#include <list>
#include <climits>
using namespace std;

struct adat {
    int csp;
    vector<int>sz;
    int lat, latv_sz;
};

vector<adat>x;
vector<pair<int, int>>y;
list<int>sol;

int n, m;

void solve(int akt)
{
    sol.push_front(akt);
    if (y[akt].first != 0) solve(y[akt].first);
}

int main()
{
    cin >> n >> m;
    x.resize(n + 1);
    y.resize(n + 1);
    for (int i = 1; i <= n; ++i)
    {
        cin >> x[i].latv_sz;
    }
    for (int i = 1; i <= m; ++i)
    {
        int a, b;
        cin >> a >> b;
        x[a].sz.push_back(b);
    }

    for (int i = 1; i <= n; ++i)
    {
        if (i == 1)
        {
            y[i].first = 0;
            y[i].second = x[i].latv_sz;
        }
        else
        {
            y[i].first = 0;
            y[i].second = INT_MIN;
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        for (auto& e : x[i].sz)
        {
            if (y[e].second <= y[i].second + x[e].latv_sz) //!
            {
                y[e].second = y[i].second + x[e].latv_sz;
                y[e].first = i;
            }
        }
    }

    solve(n);
    if (sol.front() == 1)
    {
        cout << y[n].second << endl;
        for (auto& e : sol) cout << e << " ";
    }
    else
    {
        cout << -1;
    }
}

// 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
1Elfogadva1ms316 KiB
subtask20/20
2Elfogadva1ms512 KiB
3Elfogadva2ms316 KiB
4Elfogadva1ms316 KiB
5Elfogadva6ms748 KiB
6Elfogadva3ms316 KiB
7Elfogadva8ms780 KiB
8Elfogadva8ms896 KiB
9Hibás válasz1ms316 KiB
10Hibás válasz14ms1452 KiB
11Hibás válasz1ms316 KiB
12Hibás válasz1ms332 KiB
subtask325/25
13Elfogadva1ms500 KiB
14Elfogadva1ms316 KiB
15Elfogadva1ms316 KiB
16Elfogadva2ms316 KiB
17Elfogadva1ms316 KiB
18Elfogadva1ms316 KiB
19Elfogadva1ms584 KiB
20Elfogadva1ms316 KiB
21Elfogadva1ms552 KiB
22Elfogadva3ms452 KiB
23Elfogadva2ms316 KiB
24Elfogadva4ms316 KiB
25Elfogadva2ms380 KiB
26Elfogadva2ms316 KiB
27Elfogadva4ms500 KiB
28Elfogadva27ms668 KiB
29Elfogadva4ms528 KiB
30Elfogadva28ms924 KiB
31Elfogadva17ms872 KiB
32Elfogadva35ms948 KiB
33Elfogadva10ms1332 KiB
subtask40/20
34Elfogadva1ms316 KiB
35Elfogadva1ms316 KiB
36Elfogadva2ms508 KiB
37Hibás válasz1ms316 KiB
38Hibás válasz1ms316 KiB
39Hibás válasz1ms316 KiB
40Elfogadva1ms316 KiB
41Elfogadva1ms316 KiB
42Elfogadva1ms316 KiB
43Elfogadva1ms316 KiB
44Hibás válasz1ms316 KiB
45Elfogadva1ms316 KiB
46Hibás válasz1ms316 KiB
47Hibás válasz1ms508 KiB
48Elfogadva1ms316 KiB
49Elfogadva1ms508 KiB
50Elfogadva1ms560 KiB
51Elfogadva1ms376 KiB
52Elfogadva1ms316 KiB
53Elfogadva1ms508 KiB
54Elfogadva1ms508 KiB
55Elfogadva1ms316 KiB
56Elfogadva1ms332 KiB
57Elfogadva1ms316 KiB
58Elfogadva1ms316 KiB
59Elfogadva1ms508 KiB
60Elfogadva1ms316 KiB
61Hibás válasz1ms316 KiB
62Hibás válasz1ms500 KiB
63Hibás válasz1ms316 KiB
64Hibás válasz1ms316 KiB
65Hibás válasz1ms316 KiB
66Hibás válasz1ms316 KiB
subtask50/15
67Elfogadva1ms316 KiB
68Elfogadva1ms512 KiB
69Elfogadva2ms316 KiB
70Elfogadva1ms316 KiB
71Elfogadva6ms748 KiB
72Elfogadva3ms316 KiB
73Elfogadva8ms780 KiB
74Elfogadva8ms896 KiB
75Hibás válasz1ms316 KiB
76Hibás válasz14ms1452 KiB
77Hibás válasz1ms316 KiB
78Hibás válasz1ms332 KiB
79Elfogadva1ms500 KiB
80Elfogadva1ms316 KiB
81Elfogadva1ms316 KiB
82Elfogadva2ms316 KiB
83Elfogadva1ms316 KiB
84Elfogadva1ms316 KiB
85Elfogadva1ms584 KiB
86Elfogadva1ms316 KiB
87Elfogadva1ms552 KiB
88Elfogadva3ms452 KiB
89Elfogadva2ms316 KiB
90Elfogadva4ms316 KiB
91Elfogadva2ms380 KiB
92Elfogadva2ms316 KiB
93Elfogadva4ms500 KiB
94Elfogadva27ms668 KiB
95Elfogadva4ms528 KiB
96Elfogadva28ms924 KiB
97Elfogadva17ms872 KiB
98Elfogadva35ms948 KiB
99Elfogadva10ms1332 KiB
100Elfogadva1ms316 KiB
101Elfogadva2ms508 KiB
102Hibás válasz1ms316 KiB
103Hibás válasz1ms316 KiB
104Hibás válasz1ms316 KiB
105Elfogadva1ms316 KiB
106Elfogadva1ms316 KiB
107Elfogadva1ms316 KiB
108Elfogadva1ms316 KiB
109Hibás válasz1ms316 KiB
110Elfogadva1ms316 KiB
111Hibás válasz1ms316 KiB
112Hibás válasz1ms508 KiB
113Elfogadva1ms316 KiB
114Elfogadva1ms508 KiB
115Elfogadva1ms560 KiB
116Elfogadva1ms376 KiB
117Elfogadva1ms316 KiB
118Elfogadva1ms508 KiB
119Elfogadva1ms508 KiB
120Elfogadva1ms316 KiB
121Elfogadva1ms332 KiB
122Elfogadva1ms316 KiB
123Elfogadva1ms316 KiB
124Elfogadva1ms508 KiB
125Elfogadva1ms316 KiB
126Hibás válasz1ms316 KiB
127Hibás válasz1ms500 KiB
128Hibás válasz1ms316 KiB
129Hibás válasz1ms316 KiB
130Hibás válasz1ms316 KiB
131Hibás válasz1ms316 KiB
132Elfogadva4ms380 KiB
133Elfogadva2ms316 KiB
134Elfogadva4ms316 KiB
135Hibás válasz2ms316 KiB
136Hibás válasz3ms316 KiB
137Elfogadva2ms316 KiB
138Hibás válasz3ms344 KiB
139Elfogadva3ms508 KiB
140Hibás válasz4ms504 KiB
141Hibás válasz3ms364 KiB
142Hibás válasz8ms820 KiB
143Hibás válasz9ms1060 KiB
144Hibás válasz12ms992 KiB
145Hibás válasz8ms904 KiB
146Hibás válasz20ms1648 KiB
147Hibás válasz17ms1364 KiB
148Hibás válasz16ms1076 KiB
149Hibás válasz10ms564 KiB