195782025-12-16 09:35:12szabel26Városnézéscpp17Hibás válasz 0/8035ms1624 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;
            }
        }
    }

    if (y[n].second != INT_MIN)
    {
        cout << y[n].second << endl;
        solve(n);
        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
2Elfogadva1ms316 KiB
3Elfogadva1ms512 KiB
4Elfogadva1ms316 KiB
5Elfogadva4ms748 KiB
6Elfogadva3ms348 KiB
7Elfogadva8ms1076 KiB
8Elfogadva8ms868 KiB
9Hibás válasz1ms316 KiB
10Hibás válasz14ms1552 KiB
11Hibás válasz1ms316 KiB
12Hibás válasz1ms316 KiB
subtask30/25
13Elfogadva1ms404 KiB
14Elfogadva1ms316 KiB
15Elfogadva1ms500 KiB
16Elfogadva1ms316 KiB
17Elfogadva1ms508 KiB
18Elfogadva1ms316 KiB
19Elfogadva1ms500 KiB
20Hibás válasz1ms316 KiB
21Hibás válasz1ms316 KiB
22Elfogadva3ms448 KiB
23Hibás válasz2ms492 KiB
24Elfogadva4ms560 KiB
25Elfogadva2ms316 KiB
26Hibás válasz3ms552 KiB
27Hibás válasz4ms316 KiB
28Elfogadva26ms812 KiB
29Elfogadva4ms500 KiB
30Elfogadva28ms1388 KiB
31Hibás válasz17ms880 KiB
32Hibás válasz35ms944 KiB
33Hibás válasz10ms1332 KiB
subtask40/20
34Elfogadva1ms316 KiB
35Elfogadva2ms316 KiB
36Elfogadva2ms316 KiB
37Hibás válasz2ms508 KiB
38Hibás válasz1ms316 KiB
39Hibás válasz1ms316 KiB
40Elfogadva1ms316 KiB
41Hibás válasz1ms564 KiB
42Elfogadva1ms508 KiB
43Hibás válasz1ms508 KiB
44Hibás válasz1ms316 KiB
45Elfogadva1ms316 KiB
46Hibás válasz1ms316 KiB
47Hibás válasz1ms316 KiB
48Elfogadva1ms316 KiB
49Hibás válasz1ms316 KiB
50Elfogadva1ms316 KiB
51Elfogadva1ms316 KiB
52Elfogadva1ms316 KiB
53Elfogadva1ms392 KiB
54Elfogadva1ms316 KiB
55Elfogadva1ms508 KiB
56Elfogadva1ms332 KiB
57Elfogadva1ms316 KiB
58Elfogadva1ms316 KiB
59Elfogadva1ms316 KiB
60Elfogadva1ms316 KiB
61Hibás válasz1ms316 KiB
62Hibás válasz1ms316 KiB
63Hibás válasz1ms316 KiB
64Hibás válasz1ms508 KiB
65Hibás válasz1ms316 KiB
66Hibás válasz1ms316 KiB
subtask50/15
67Elfogadva1ms316 KiB
68Elfogadva1ms316 KiB
69Elfogadva1ms512 KiB
70Elfogadva1ms316 KiB
71Elfogadva4ms748 KiB
72Elfogadva3ms348 KiB
73Elfogadva8ms1076 KiB
74Elfogadva8ms868 KiB
75Hibás válasz1ms316 KiB
76Hibás válasz14ms1552 KiB
77Hibás válasz1ms316 KiB
78Hibás válasz1ms316 KiB
79Elfogadva1ms404 KiB
80Elfogadva1ms316 KiB
81Elfogadva1ms500 KiB
82Elfogadva1ms316 KiB
83Elfogadva1ms508 KiB
84Elfogadva1ms316 KiB
85Elfogadva1ms500 KiB
86Hibás válasz1ms316 KiB
87Hibás válasz1ms316 KiB
88Elfogadva3ms448 KiB
89Hibás válasz2ms492 KiB
90Elfogadva4ms560 KiB
91Elfogadva2ms316 KiB
92Hibás válasz3ms552 KiB
93Hibás válasz4ms316 KiB
94Elfogadva26ms812 KiB
95Elfogadva4ms500 KiB
96Elfogadva28ms1388 KiB
97Hibás válasz17ms880 KiB
98Hibás válasz35ms944 KiB
99Hibás válasz10ms1332 KiB
100Elfogadva2ms316 KiB
101Elfogadva2ms316 KiB
102Hibás válasz2ms508 KiB
103Hibás válasz1ms316 KiB
104Hibás válasz1ms316 KiB
105Elfogadva1ms316 KiB
106Hibás válasz1ms564 KiB
107Elfogadva1ms508 KiB
108Hibás válasz1ms508 KiB
109Hibás válasz1ms316 KiB
110Elfogadva1ms316 KiB
111Hibás válasz1ms316 KiB
112Hibás válasz1ms316 KiB
113Elfogadva1ms316 KiB
114Hibás válasz1ms316 KiB
115Elfogadva1ms316 KiB
116Elfogadva1ms316 KiB
117Elfogadva1ms316 KiB
118Elfogadva1ms392 KiB
119Elfogadva1ms316 KiB
120Elfogadva1ms508 KiB
121Elfogadva1ms332 KiB
122Elfogadva1ms316 KiB
123Elfogadva1ms316 KiB
124Elfogadva1ms316 KiB
125Elfogadva1ms316 KiB
126Hibás válasz1ms316 KiB
127Hibás válasz1ms316 KiB
128Hibás válasz1ms316 KiB
129Hibás válasz1ms508 KiB
130Hibás válasz1ms316 KiB
131Hibás válasz1ms316 KiB
132Elfogadva3ms316 KiB
133Elfogadva2ms316 KiB
134Elfogadva4ms316 KiB
135Hibás válasz2ms316 KiB
136Hibás válasz3ms316 KiB
137Hibás válasz2ms316 KiB
138Hibás válasz3ms420 KiB
139Elfogadva3ms508 KiB
140Hibás válasz4ms564 KiB
141Hibás válasz3ms500 KiB
142Hibás válasz8ms820 KiB
143Hibás válasz9ms1036 KiB
144Hibás válasz12ms1076 KiB
145Hibás válasz8ms836 KiB
146Hibás válasz20ms1624 KiB
147Hibás válasz17ms1364 KiB
148Hibás válasz16ms932 KiB
149Hibás válasz9ms564 KiB