195842025-12-16 10:25:46szabel26Városnézéscpp17Accepted 80/80120ms1684 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 latv_sz, honnan;
};

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

int n, m;

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

void dijkstra(int akt)
{
    for (auto& e : x[akt].sz)
    {
        if (y[e] < y[akt] + x[e].latv_sz)
        {
            x[e].honnan = akt;
            y[e] = y[akt] + x[e].latv_sz;
            dijkstra(e);
        }
    }
}

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)
        {
            x[i].honnan = 0;
            y[i] = x[i].latv_sz;
        }
        else
        {
            x[i].honnan = 0;
            y[i] = INT_MIN;
        }
    }

    dijkstra(1);

    solve(n);
    if (sol.front() == 1)
    {
        cout << y[n] << 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
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
subtask220/20
2Accepted1ms316 KiB
3Accepted1ms316 KiB
4Accepted1ms316 KiB
5Accepted4ms564 KiB
6Accepted3ms316 KiB
7Accepted8ms784 KiB
8Accepted8ms852 KiB
9Accepted1ms316 KiB
10Accepted14ms1684 KiB
11Accepted1ms316 KiB
12Accepted1ms316 KiB
subtask325/25
13Accepted1ms316 KiB
14Accepted1ms316 KiB
15Accepted1ms332 KiB
16Accepted1ms316 KiB
17Accepted1ms316 KiB
18Accepted1ms316 KiB
19Accepted1ms316 KiB
20Accepted1ms316 KiB
21Accepted1ms316 KiB
22Accepted4ms332 KiB
23Accepted2ms316 KiB
24Accepted4ms500 KiB
25Accepted2ms316 KiB
26Accepted3ms560 KiB
27Accepted4ms476 KiB
28Accepted28ms748 KiB
29Accepted4ms352 KiB
30Accepted28ms816 KiB
31Accepted16ms820 KiB
32Accepted34ms1076 KiB
33Accepted9ms1236 KiB
subtask420/20
34Accepted1ms316 KiB
35Accepted1ms508 KiB
36Accepted1ms316 KiB
37Accepted1ms500 KiB
38Accepted1ms316 KiB
39Accepted1ms316 KiB
40Accepted1ms316 KiB
41Accepted1ms508 KiB
42Accepted1ms500 KiB
43Accepted1ms512 KiB
44Accepted1ms316 KiB
45Accepted1ms316 KiB
46Accepted1ms316 KiB
47Accepted1ms316 KiB
48Accepted1ms316 KiB
49Accepted1ms316 KiB
50Accepted1ms316 KiB
51Accepted1ms316 KiB
52Accepted1ms316 KiB
53Accepted1ms316 KiB
54Accepted1ms316 KiB
55Accepted1ms316 KiB
56Accepted1ms316 KiB
57Accepted1ms540 KiB
58Accepted1ms508 KiB
59Accepted1ms316 KiB
60Accepted1ms360 KiB
61Accepted1ms316 KiB
62Accepted1ms316 KiB
63Accepted1ms316 KiB
64Accepted1ms536 KiB
65Accepted1ms368 KiB
66Accepted1ms316 KiB
subtask515/15
67Accepted1ms316 KiB
68Accepted1ms316 KiB
69Accepted1ms316 KiB
70Accepted1ms316 KiB
71Accepted4ms564 KiB
72Accepted3ms316 KiB
73Accepted8ms784 KiB
74Accepted8ms852 KiB
75Accepted1ms316 KiB
76Accepted14ms1684 KiB
77Accepted1ms316 KiB
78Accepted1ms316 KiB
79Accepted1ms316 KiB
80Accepted1ms316 KiB
81Accepted1ms332 KiB
82Accepted1ms316 KiB
83Accepted1ms316 KiB
84Accepted1ms316 KiB
85Accepted1ms316 KiB
86Accepted1ms316 KiB
87Accepted1ms316 KiB
88Accepted4ms332 KiB
89Accepted2ms316 KiB
90Accepted4ms500 KiB
91Accepted2ms316 KiB
92Accepted3ms560 KiB
93Accepted4ms476 KiB
94Accepted28ms748 KiB
95Accepted4ms352 KiB
96Accepted28ms816 KiB
97Accepted16ms820 KiB
98Accepted34ms1076 KiB
99Accepted9ms1236 KiB
100Accepted1ms508 KiB
101Accepted1ms316 KiB
102Accepted1ms500 KiB
103Accepted1ms316 KiB
104Accepted1ms316 KiB
105Accepted1ms316 KiB
106Accepted1ms508 KiB
107Accepted1ms500 KiB
108Accepted1ms512 KiB
109Accepted1ms316 KiB
110Accepted1ms316 KiB
111Accepted1ms316 KiB
112Accepted1ms316 KiB
113Accepted1ms316 KiB
114Accepted1ms316 KiB
115Accepted1ms316 KiB
116Accepted1ms316 KiB
117Accepted1ms316 KiB
118Accepted1ms316 KiB
119Accepted1ms316 KiB
120Accepted1ms316 KiB
121Accepted1ms316 KiB
122Accepted1ms540 KiB
123Accepted1ms508 KiB
124Accepted1ms316 KiB
125Accepted1ms360 KiB
126Accepted1ms316 KiB
127Accepted1ms316 KiB
128Accepted1ms316 KiB
129Accepted1ms536 KiB
130Accepted1ms368 KiB
131Accepted1ms316 KiB
132Accepted4ms316 KiB
133Accepted2ms480 KiB
134Accepted4ms316 KiB
135Accepted2ms316 KiB
136Accepted3ms316 KiB
137Accepted2ms508 KiB
138Accepted3ms508 KiB
139Accepted3ms316 KiB
140Accepted6ms564 KiB
141Accepted3ms316 KiB
142Accepted8ms836 KiB
143Accepted10ms984 KiB
144Accepted12ms1128 KiB
145Accepted8ms868 KiB
146Accepted21ms1632 KiB
147Accepted19ms1560 KiB
148Accepted120ms1388 KiB
149Accepted14ms976 KiB