Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <fstream>
- #include <algorithm>
- #include <array>
- #include <queue>
- #include <vector>
- using namespace std;
- ifstream cin("joc.in");
- ofstream cout("joc.out");
- typedef long long ll;
- const ll mxN = 5e4, INF = 1e16;
- priority_queue<array<ll,2>> pq;
- vector<int> adj[mxN+10], sol;
- bool visited[mxN+10];
- ll nivel[mxN+10], d[mxN+10], parent[mxN+10];
- int main()
- {
- int cerinta;
- cin >> cerinta;
- int n , s, f;
- cin >> n >> s >> f;
- for(int i = 1;i<=n;i++)
- cin >> nivel[i];
- for(int from = 1;from <= n;from++)
- {
- int k; cin >> k;
- for(int it = 1;it<=k;it++)
- {
- int to; cin >> to;
- adj[from].push_back(to);
- }
- }
- for(int i = 1;i<=n;i++)
- d[i] = INF;
- d[s] = 0;
- pq.push({0,s});
- while(!pq.empty())
- {
- int from = pq.top()[1];
- pq.pop();
- if(visited[from])
- continue;
- visited[from] = true;
- for(auto it : adj[from])
- {
- int to = it;
- int nivelA = nivel[from];
- int nivelB = nivel[to];
- if(nivelA < nivelB) swap(nivelA,nivelB);
- ll cost = nivelA / nivelB;
- if(d[from] + cost < d[to])
- {
- parent[to] = from;
- d[to] = d[from] + cost;
- pq.push({-d[to],to});
- }
- }
- }
- if(cerinta == 1)
- cout << d[f] << '\n';
- else
- {
- for(int p = f;p!=0;p = parent[p])
- sol.push_back(p);
- reverse(sol.begin(),sol.end());
- cout << sol.size() << '\n';
- for(auto it : sol)
- cout << it << ' ';
- }
- return 0;
- }
Advertisement
Advertisement
