Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- vector<pair<int, int>> graf[512];
- priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, std::greater<pair<int, pair<int, int>>>> q;
- int cost[512];
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- memset(cost, 0x3f3f3f3f, sizeof(cost));
- int t, l, o, d, temp;
- cin >> t >> l >> o >> d;
- vector<bool> marca(t, false);
- for(int i = 0; i < l; i++) {
- int k, uk;
- cin >> k >> uk;
- if(uk == o) {
- temp = i;
- }
- for(int j = 1; j < k; j++) {
- int v;
- cin >> v;
- if(v == o) {
- temp = i;
- }
- graf[uk].push_back(make_pair(v, i));
- graf[v].push_back(make_pair(uk, i));
- }
- }
- cost[o] = 1;
- q.push(make_pair(1, make_pair(o, temp)));
- while(!q.empty()) {
- pair<int, pair<int, int>> p = q.top();
- q.pop();
- int c = p.first, a = p.second.first;
- if(!marca[a]) {
- cost[a] = c;
- marca[a] = true;
- for(auto e : graf[a]) {
- int b = e.first, dd = e.second;
- if(!marca[b]) {
- if(dd == p.second.second) {
- q.push(make_pair(c, make_pair(b, dd)));
- } else {
- q.push(make_pair(c + 1, make_pair(b, dd)));
- }
- }
- }
- }
- }
- cout << cost[d] << "\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement