Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <string>
- #include <fstream>
- #include <cstdlib>
- #include <queue>
- #include <string.h>
- #include <algorithm>
- using namespace std;
- int main() {
- int n, m;
- cin >> n >> m;
- vector < vector<int> > g(m);
- for(int i = 0; i < n; i++) {
- int len, s, to;
- cin >> len;
- cin >> s;
- s--;
- len--;
- for(int j = 0; j < len; j++) {
- cin >> to;
- to--;
- g[s].push_back(to);
- g[to].push_back(s);
- s = to;
- }
- }
- int start, finish = 0, r;
- cin >> r;
- vector < pair <int, int> > startPoints(r);
- for (auto &i : startPoints) {
- cin >> i.first >> i.second;
- i.first--;
- }
- int k;
- cin >> k;
- vector < pair <int, int> > finishPoints(k);
- for(auto &i : finishPoints)
- cin >> i.first >> i.second;
- vector <int> ansPath;
- int ansMin = 1e9;
- for (int i = 0; i < r; i++) {
- start = startPoints[i].first;
- queue<int> q;
- int d[m], p[m];
- bool used[m];
- memset(used, false, sizeof used);
- memset(d, 0, sizeof d);
- memset(p, 0, sizeof m);
- q.push(start);
- d[start] = startPoints[i].second;
- p[start] = -1;
- used[start] = true;
- while (!q.empty()) {
- int v = q.front();
- q.pop();
- for(int i = 0; i < g[v].size(); i++) {
- int to = g[v][i];
- if(!used[to]) {
- q.push(to);
- d[to] = d[v] + 1;
- p[to] = v;
- used[to] = true;
- }
- }
- }
- int minn = 1e9;
- for(auto i : finishPoints) {
- if(d[i.first - 1] + i.second < minn) {
- minn = d[i.first - 1] + i.second;
- finish = i.first - 1;
- }
- }
- if(minn < ansMin) {
- ansMin = minn;
- vector <int> path;
- for (int v = finish; v != -1; v = p[v])
- path.push_back (v);
- reverse (path.begin(), path.end());
- ansPath = path;
- }
- }
- cout << ansMin << endl;
- for (auto i : ansPath)
- cout << i + 1 << ' ';
- cout << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement