217842026-01-13 22:07:08szabelrVárosnézéscpp17Runtime error 20/80533ms262144 KiB
// Városnézés topologia.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n + 1);
    vector<int> latv(n + 1);
    vector<int> indegree(n + 1,0);
    vector<int> maxlatv(n + 1,-1);
    vector<int>honnan(n + 1);
    honnan[1] = -1;
    for (int i = 1; i <= n; i++)
    {
        int x; cin >> x;
        latv[i] = x;
    }
    maxlatv[1] = latv[1];
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        adj[x].push_back(y);
        indegree[y]++;
    }
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (indegree[i] == 0) {
            q.push(i);
        }
    }
    while (!q.empty())
    {
        int v = q.front();
        q.pop();
        for (auto next : adj[v])
        {
            indegree[next]--;
            if (maxlatv[v] + latv[next] > maxlatv[next])
            {
                maxlatv[next] = maxlatv[v] + latv[next];
                honnan[next] = v;
            }
            if (indegree[next] == 0)
            {
                q.push(next);
            }
        }
    }
    cout << maxlatv[n] << endl;
    if(maxlatv[n]!=-1)
    {
        int x = honnan[n];
        vector<int>res;
        res.push_back(n);
        while (x != -1)
        {
            res.push_back(x);
            x = honnan[x];
        }
        reverse(res.begin(), res.end());
        for (auto x : res)
            cout << x << " ";
    }
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
subtask220/20
2Accepted1ms316 KiB
3Accepted1ms500 KiB
4Accepted1ms500 KiB
5Accepted3ms568 KiB
6Accepted2ms316 KiB
7Accepted4ms744 KiB
8Accepted4ms780 KiB
9Accepted1ms316 KiB
10Accepted6ms1216 KiB
11Accepted1ms316 KiB
12Accepted1ms316 KiB
subtask30/25
13Accepted1ms544 KiB
14Accepted1ms316 KiB
15Accepted1ms316 KiB
16Accepted1ms508 KiB
17Accepted1ms316 KiB
18Accepted1ms316 KiB
19Runtime error418ms262144 KiB
20Runtime error531ms262144 KiB
21Runtime error405ms262144 KiB
22Runtime error523ms262144 KiB
23Runtime error416ms262144 KiB
24Runtime error528ms262144 KiB
25Runtime error405ms262144 KiB
26Runtime error465ms262144 KiB
27Runtime error414ms262144 KiB
28Runtime error529ms262144 KiB
29Runtime error405ms262144 KiB
30Runtime error533ms262144 KiB
31Runtime error419ms262144 KiB
32Runtime error526ms262144 KiB
33Runtime error411ms262144 KiB
subtask40/20
34Accepted1ms316 KiB
35Accepted1ms564 KiB
36Accepted1ms508 KiB
37Accepted1ms316 KiB
38Accepted1ms364 KiB
39Accepted1ms316 KiB
40Accepted1ms384 KiB
41Runtime error514ms262144 KiB
42Accepted1ms364 KiB
43Runtime error404ms262144 KiB
44Accepted1ms316 KiB
45Accepted1ms356 KiB
46Accepted1ms332 KiB
47Accepted1ms316 KiB
48Accepted1ms316 KiB
49Runtime error507ms262144 KiB
50Accepted1ms316 KiB
51Accepted1ms316 KiB
52Accepted1ms316 KiB
53Accepted1ms316 KiB
54Accepted1ms316 KiB
55Accepted1ms316 KiB
56Accepted1ms316 KiB
57Accepted1ms316 KiB
58Accepted1ms508 KiB
59Accepted1ms316 KiB
60Accepted1ms316 KiB
61Accepted1ms500 KiB
62Accepted1ms500 KiB
63Accepted1ms316 KiB
64Accepted1ms316 KiB
65Accepted1ms316 KiB
66Accepted1ms316 KiB
subtask50/15
67Accepted1ms316 KiB
68Accepted1ms316 KiB
69Accepted1ms500 KiB
70Accepted1ms500 KiB
71Accepted3ms568 KiB
72Accepted2ms316 KiB
73Accepted4ms744 KiB
74Accepted4ms780 KiB
75Accepted1ms316 KiB
76Accepted6ms1216 KiB
77Accepted1ms316 KiB
78Accepted1ms316 KiB
79Accepted1ms544 KiB
80Accepted1ms316 KiB
81Accepted1ms316 KiB
82Accepted1ms508 KiB
83Accepted1ms316 KiB
84Accepted1ms316 KiB
85Runtime error418ms262144 KiB
86Runtime error531ms262144 KiB
87Runtime error405ms262144 KiB
88Runtime error523ms262144 KiB
89Runtime error416ms262144 KiB
90Runtime error528ms262144 KiB
91Runtime error405ms262144 KiB
92Runtime error465ms262144 KiB
93Runtime error414ms262144 KiB
94Runtime error529ms262144 KiB
95Runtime error405ms262144 KiB
96Runtime error533ms262144 KiB
97Runtime error419ms262144 KiB
98Runtime error526ms262144 KiB
99Runtime error411ms262144 KiB
100Accepted1ms564 KiB
101Accepted1ms508 KiB
102Accepted1ms316 KiB
103Accepted1ms364 KiB
104Accepted1ms316 KiB
105Accepted1ms384 KiB
106Runtime error514ms262144 KiB
107Accepted1ms364 KiB
108Runtime error404ms262144 KiB
109Accepted1ms316 KiB
110Accepted1ms356 KiB
111Accepted1ms332 KiB
112Accepted1ms316 KiB
113Accepted1ms316 KiB
114Runtime error507ms262144 KiB
115Accepted1ms316 KiB
116Accepted1ms316 KiB
117Accepted1ms316 KiB
118Accepted1ms316 KiB
119Accepted1ms316 KiB
120Accepted1ms316 KiB
121Accepted1ms316 KiB
122Accepted1ms316 KiB
123Accepted1ms508 KiB
124Accepted1ms316 KiB
125Accepted1ms316 KiB
126Accepted1ms500 KiB
127Accepted1ms500 KiB
128Accepted1ms316 KiB
129Accepted1ms316 KiB
130Accepted1ms316 KiB
131Accepted1ms316 KiB
132Runtime error509ms262144 KiB
133Accepted2ms316 KiB
134Accepted2ms316 KiB
135Runtime error402ms262144 KiB
136Accepted2ms316 KiB
137Runtime error398ms262144 KiB
138Accepted2ms508 KiB
139Accepted2ms316 KiB
140Accepted3ms704 KiB
141Accepted2ms316 KiB
142Accepted4ms820 KiB
143Accepted4ms820 KiB
144Accepted6ms1076 KiB
145Accepted4ms820 KiB
146Accepted8ms1588 KiB
147Accepted8ms1332 KiB
148Accepted8ms1076 KiB
149Accepted4ms564 KiB