多數(shù)題解是錯(cuò)的，因?yàn)閔du上的這道題的數(shù)據(jù)比較水才可以過，可以試試discuss里給的數(shù)據(jù)，下面這幾個(gè)題解比較靠譜。

    http://blog.csdn.net/nash142857/article/details/8253913

    http://www.cnblogs.com/crisxyj/archive/2013/03/10/2952396.html

    http://hi.baidu.com/novosbirsk/item/bfcf0cd201edfc2d39f6f709

    兩份代碼的思想是完全一樣的，只是“baidu blog”那份用w[i][e]來判斷i的最短路樹是否包括邊e，而cnblog的那份是用used[x][u][v]來判斷邊u-->v是否xxx.

#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <deque>
using namespace std;
#define     MAXN    101
#define     INF     99999999
#define     debug   printf("!\n")
struct Edge { int u,v; } edge[3001];
vector<int> vertex[MAXN];
int visit[MAXN], sum[MAXN], cnt[MAXN][MAXN];        //cnt[u][v]表u--v的邊有多少條，用來處理重邊
bool used[MAXN][MAXN][MAXN];                        //used[x][u][v]x的最短路樹是否用到了邊u--v
int n, m;

void init();
void dijkstra(int s, int when, int flag);
int main()
{
    int when = 0;
    int u, v;
    while(scanf("%d%d", &n, &m) != EOF) {
        init();
        for(int i = 0; i < m; i++) {
            scanf("%d%d", &u, &v);
            vertex[u].push_back(v);
            vertex[v].push_back(u);
            edge[i].u = u, edge[i].v = v;
            cnt[u][v]++, cnt[v][u]++;
        }
        int ans = 0;
        for(int i = 1; i <= n; i++) {
            dijkstra(i, ++when, 1);
            ans += sum[i];
        }
        for(int i = 0; i < m; i++) {
            int tmp = ans;
            int u = edge[i].u, v = edge[i].v;
            //forbid_u = edge[i].u, forbid_v = edge[i].v;       因?yàn)橛兄剡吽圆荒苡眠@種方法
            for(int j = 1; j <= n; j++) if(used[j][u][v] && cnt[u][v] == 1) {       //不加cnt[u][v] == 1會(huì)超時(shí)。。卡的就是重邊，靠！
                int tmp = sum[j];
                sum[j] = 0;
                //vector<int> :: iterator it1 = find(vertex[u].begin(), vertex[u].end(), v);
                //vector<int> :: iterator it2 = find(vertex[v].begin(), vertex[v].end(), u);
                //*it1 = u, *it2 = v;
                cnt[u][v]--, cnt[v][u]--;
                dijkstra(j, ++when, 2);
                cnt[u][v]++, cnt[v][u]++;
                //*it1 = v, *it2 = u;     //本來是用erase的，超時(shí)了。 現(xiàn)在換這種方法也超時(shí)了，估計(jì)find耗時(shí)太久。
                ans = ans - tmp + sum[j];   //用新的sum[j]來代替舊的tmp
                sum[j] = tmp;
                int k ;
                for(k = 1; k <= n; k++) if(visit[k] != when) break;     //如果刪邊了以后j不能到達(dá)k(即k沒有進(jìn)過隊(duì))
                if(k <= n) {
                    ans = INF;
                    break;
                }
            }
            ans == INF ? printf("INF\n") : printf("%d\n", ans);
            ans = tmp;  //不要把這個(gè)tmp和for_j里的tmp混了..
        }
        for(int i = 0; i < m; i++) cnt[edge[i].u][edge[i].v] = cnt[edge[i].v][edge[i].u] = 0;   //初始化因?yàn)楦杏Xmemset(cnt)會(huì)不會(huì)花更多時(shí)間
    }
    return 0;
}
void dijkstra(int s, int when, int flag)
{
    int floors = 1;
    int cur = 0;
    deque<int> Q[2];
    Q[cur].push_back(s);
    visit[s] = when;
    do {
        while(!Q[cur].empty()) {
            int u = Q[cur].front();
            Q[cur].pop_front();
            for(int Size = vertex[u].size(), i = 0; i < Size; i++) {
                int v = vertex[u][i];
                if(visit[v] != when && cnt[u][v] > 0) {
                    if(flag == 1) used[s][u][v] = used[s][v][u] = true;   //第一次最短路才標(biāo)記used因?yàn)閼械脤憙杀椋砸猣lag來標(biāo)記是刪邊前還收刪邊后做的最短路，1則是預(yù)處理時(shí)的最短路，此時(shí)要標(biāo)記used；2則是刪邊后的最短路，這個(gè)時(shí)候不能標(biāo)記used.
                    visit[v] = when;
                    sum[s] += floors;
                    Q[1-cur].push_back(v);
                }
            }
        }
        floors++; 
        cur = 1 - cur;
    } while(!Q[cur].empty());
}
void init()
{
    memset(sum, 0, sizeof(sum));
    memset(used, false, sizeof(used));
    for(int i = 1; i <= n; i++) vertex[i].clear();
}

#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) {     //是否已入隊(duì)
                    //max_d[to] = max(max_d[to], max_d[at]+1);      這句是不對(duì)的，因?yàn)檫@個(gè)分層跟拓?fù)渑判虻姆謱邮遣灰粯拥模負(fù)渑判蚴且谌攵葹?時(shí)才能加進(jìn)隊(duì)Q，所以可以這樣寫，但是這里只要第一次遇見點(diǎn)to就必須得入隊(duì)，因?yàn)橐氖亲疃搪窂?/span>
                    max_d[to] = max(max_d[to], floors); //不把這句放在if外面，因?yàn)檫@里的max_d[to]是距離s的最短路徑，最短路徑也就是最小層數(shù)，最小層數(shù)在to第一次入隊(duì)的時(shí)候已經(jīng)得到了
                    visit[to] = when;
                    Q[1-cur].push_back(to);
                }
            }
        }
        cur = 1 - cur;
    } while(!Q[cur].empty());
}