186232025-10-29 12:16:00KristófVárosnézéscpp17Wrong answer 20/801.098s262144 KiB
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

void dfs(int s , vector<vector<int>> &graph,vector<vector<int>> &graph2,vector<int> &indegs)
{
for(auto x : graph[s])
    {
    graph2[s].push_back(x);
    indegs[x]++;
    dfs(x,graph,graph2,indegs);
    }
}




int main()
{
    int n,m;
    cin>>n>>m;
    vector<vector<int>> graph(n+1);
    vector<vector<int>> graph2(n+1);
    vector<int> weight(n+1,0);
    vector<int> parent(n+1,0);
    vector<int> dp(n+1,-1);
    queue<int> to;
    int x,y;
    vector<int> indegs(n+1,0);
    for(int i=1;i<=n;i++)
        {
        cin>>weight[i];
        }
    for(int i=1;i<=m;i++)
        {
        cin>>x>>y;
        graph[x].push_back(y);
        //indegs[y]++;
        }
    dfs(1,graph,graph2,indegs);
    for(int i=1;i<=n;i++)
        {
        if(indegs[i]==0)
            {
            to.push(i);
            dp[i]=weight[i];
            }
        }
    int curr;
    while(!to.empty())
        {
        curr=to.front();to.pop();
        for(auto x : graph2[curr])
            {
            indegs[x]--;
            if(indegs[x]==0)
                {
                to.push(x);
                }
            if(dp[x]<dp[curr]+weight[x])
                {
                parent[x]=curr;
                dp[x]=dp[curr]+weight[x];
                }
            }
        }
    cout<<dp[n]<<endl;
    if(dp[n]==-1)
        {
        return 0;
        }
    else
        {
        vector<int> ans;
        int i=n;
        ans.push_back(n);
        while(parent[i])
            {
            ans.push_back(parent[i]);
            i=parent[i];
            }
        for(int i=ans.size()-1;i>-1;--i)
            {
            cout<<ans[i]<<" ";
            }
        }
    return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
subtask220/20
2Accepted1ms508 KiB
3Accepted1ms316 KiB
4Accepted1ms508 KiB
5Accepted6ms820 KiB
6Accepted3ms516 KiB
7Accepted9ms1332 KiB
8Accepted9ms1104 KiB
9Accepted1ms316 KiB
10Accepted17ms2304 KiB
11Accepted1ms316 KiB
12Accepted2ms316 KiB
subtask30/25
13Accepted1ms316 KiB
14Accepted1ms316 KiB
15Accepted1ms316 KiB
16Accepted2ms564 KiB
17Accepted1ms316 KiB
18Accepted1ms508 KiB
19Accepted1ms316 KiB
20Wrong answer1ms540 KiB
21Wrong answer1ms316 KiB
22Runtime error957ms262144 KiB
23Wrong answer2ms316 KiB
24Runtime error810ms262144 KiB
25Accepted35ms9664 KiB
26Wrong answer2ms368 KiB
27Wrong answer4ms316 KiB
28Runtime error837ms262144 KiB
29Accepted14ms2948 KiB
30Runtime error796ms262144 KiB
31Wrong answer17ms820 KiB
32Wrong answer35ms1076 KiB
33Wrong answer10ms1624 KiB
subtask40/20
34Accepted1ms316 KiB
35Accepted1ms316 KiB
36Accepted1ms508 KiB
37Accepted1ms316 KiB
38Accepted2ms564 KiB
39Accepted1ms316 KiB
40Accepted1ms508 KiB
41Wrong answer1ms328 KiB
42Wrong answer1ms316 KiB
43Wrong answer1ms316 KiB
44Accepted2ms564 KiB
45Wrong answer1ms316 KiB
46Accepted8ms2024 KiB
47Accepted1ms316 KiB
48Wrong answer1ms316 KiB
49Wrong answer1ms316 KiB
50Accepted1ms316 KiB
51Accepted1ms316 KiB
52Accepted1ms500 KiB
53Accepted1ms316 KiB
54Accepted1ms508 KiB
55Accepted1ms316 KiB
56Accepted1ms336 KiB
57Accepted1ms316 KiB
58Accepted1ms316 KiB
59Accepted1ms316 KiB
60Accepted1ms316 KiB
61Accepted1ms316 KiB
62Accepted1ms404 KiB
63Accepted1ms316 KiB
64Accepted1ms316 KiB
65Accepted1ms316 KiB
66Accepted1ms316 KiB
subtask50/15
67Accepted1ms316 KiB
68Accepted1ms508 KiB
69Accepted1ms316 KiB
70Accepted1ms508 KiB
71Accepted6ms820 KiB
72Accepted3ms516 KiB
73Accepted9ms1332 KiB
74Accepted9ms1104 KiB
75Accepted1ms316 KiB
76Accepted17ms2304 KiB
77Accepted1ms316 KiB
78Accepted2ms316 KiB
79Accepted1ms316 KiB
80Accepted1ms316 KiB
81Accepted1ms316 KiB
82Accepted2ms564 KiB
83Accepted1ms316 KiB
84Accepted1ms508 KiB
85Accepted1ms316 KiB
86Wrong answer1ms540 KiB
87Wrong answer1ms316 KiB
88Runtime error957ms262144 KiB
89Wrong answer2ms316 KiB
90Runtime error810ms262144 KiB
91Accepted35ms9664 KiB
92Wrong answer2ms368 KiB
93Wrong answer4ms316 KiB
94Runtime error837ms262144 KiB
95Accepted14ms2948 KiB
96Runtime error796ms262144 KiB
97Wrong answer17ms820 KiB
98Wrong answer35ms1076 KiB
99Wrong answer10ms1624 KiB
100Accepted1ms316 KiB
101Accepted1ms508 KiB
102Accepted1ms316 KiB
103Accepted2ms564 KiB
104Accepted1ms316 KiB
105Accepted1ms508 KiB
106Wrong answer1ms328 KiB
107Wrong answer1ms316 KiB
108Wrong answer1ms316 KiB
109Accepted2ms564 KiB
110Wrong answer1ms316 KiB
111Accepted8ms2024 KiB
112Accepted1ms316 KiB
113Wrong answer1ms316 KiB
114Wrong answer1ms316 KiB
115Accepted1ms316 KiB
116Accepted1ms316 KiB
117Accepted1ms500 KiB
118Accepted1ms316 KiB
119Accepted1ms508 KiB
120Accepted1ms316 KiB
121Accepted1ms336 KiB
122Accepted1ms316 KiB
123Accepted1ms316 KiB
124Accepted1ms316 KiB
125Accepted1ms316 KiB
126Accepted1ms316 KiB
127Accepted1ms404 KiB
128Accepted1ms316 KiB
129Accepted1ms316 KiB
130Accepted1ms316 KiB
131Accepted1ms316 KiB
132Runtime error958ms262144 KiB
133Wrong answer2ms316 KiB
134Runtime error869ms262144 KiB
135Accepted514ms151016 KiB
136Runtime error771ms262144 KiB
137Wrong answer4ms1332 KiB
138Runtime error754ms262144 KiB
139Wrong answer3ms316 KiB
140Accepted6ms820 KiB
141Accepted3ms564 KiB
142Accepted10ms1076 KiB
143Accepted17ms2400 KiB
144Accepted14ms1592 KiB
145Accepted9ms1368 KiB
146Accepted26ms2612 KiB
147Time limit exceeded1.098s163224 KiB
148Runtime error883ms262144 KiB
149Runtime error888ms262144 KiB