/*
最短路, 終點集合到s的最遠距離最短,求s. 即已知終點集opcpnfe求一s使得Min{ max{ dis(s, di) } }
好題
思路: 多次單源最短路,選出最大值
在對每個x進行分層搜索的過程中, 用max_d[y]記錄每個地區(qū)x到達地區(qū)y的最短距離中的最大值. 最后求得的Star Value就是max_d[]中的最小值.
由于題目的特殊性`邊權(quán)都為1`,所以可以借助這一性質(zhì)變換一下SPFA使其更快。
說個題外話,在臨高時看到有個學(xué)弟拓撲排序用到“分層思想”,一直覺得很妙。就是拓撲后我們可以得到floor[i],如果floor[i] > floor[j],即說明j是i的前驅(qū)節(jié)點(層數(shù)越小越接近root); 而floor[i] == floor[j]的話則i,j的相對順序無所謂,因為他們都在“同一層”。
這里因為邊權(quán)都為1,所以SPFA可以用到上述的分層思想,層數(shù)越高,離source越遠。代碼里面floors就表示層數(shù),Q是滾動隊列,就是一層一層地relax后繼節(jié)點。
注意!!千萬不要以為max_d[]是最短路算法里面的dis[],這里的max_d[i]是到點i到終點集合{di}的最大值!而常規(guī)最短路算法里的dis[]已經(jīng)被省略為“層數(shù)”了,不需要記錄,所以沒開數(shù)組。
最重要的是學(xué)到一個tip!!以前我做多次最短路的時候總要每次都初始化visit[] -> false,但其實不用的,我們只要用一個變量when表示“這是第幾次做SPFA(或其他)“,然后每次入隊前都看”是否當(dāng)前visit[v] == when就可以直到改點是否已經(jīng)入過隊......
*/
#include <stdio.h>
#include <string.h>
#include <vector>
#include <deque>
using namespace std;
#define debug printf("!\n")
#define INF 999999999
#define MAXN 10000
int n;
int max_d[MAXN];
int visit[MAXN];
vector<int> v[MAXN];
void SPFA(int s, int when);
void init();
int main()
{
int cases, query, id, m, y, x;
scanf("%d", &cases);
while(cases--) {
scanf("%d%d", &n, &query);
init();
for(int i = 0; i < n; i++) {
scanf("%d%d", &id, &m);
while(m--) {
scanf("%d", &y);
v[id].push_back(y);
}
}
int when = 0;
while(query--) {
scanf("%d", &m);
while(m--) {
scanf("%d", &x);
SPFA(x, ++when);
}
}
int ans = INF, ans_id = -1;
for(int i = 1; i < MAXN; i++) if(!v[i].empty() && max_d[i] < ans) ans = max_d[i], ans_id = i;
printf("%d %d\n", ans, ans_id);
}
return 0;
}
void init()
{
for(int i = 0; i < MAXN; i++) v[i].clear();
memset(max_d, 0, sizeof(max_d));
memset(visit, 0, sizeof(visit));
}
void SPFA(int s, int when)
{
deque<int> Q[2];
int cur = 0;
Q[cur].push_back(s);
max_d[s] = max(max_d[s], 1);
visit[s] = when;
int floors = 1;
do {
floors++;
while(!Q[cur].empty()) {
int at = Q[cur].front();
Q[cur].pop_front();
for(int Size = v[at].size(), i = 0; i < Size; i++) {
int to = v[at][i];
if(visit[to] != when) { //是否已入隊
//max_d[to] = max(max_d[to], max_d[at]+1); 這句是不對的,因為這個分層跟拓撲排序的分層是不一樣的,拓撲排序是要在入度為0時才能加進隊Q,所以可以這樣寫,但是這里只要第一次遇見點to就必須得入隊,因為要的是最短路徑
max_d[to] = max(max_d[to], floors); //不把這句放在if外面,因為這里的max_d[to]是距離s的最短路徑,最短路徑也就是最小層數(shù),最小層數(shù)在to第一次入隊的時候已經(jīng)得到了
visit[to] = when;
Q[1-cur].push_back(to);
}
}
}
cur = 1 - cur;
} while(!Q[cur].empty());
}