Meeting

/*hdu 5521 最短路problem:给你n个点的图,甲在1,乙在n. 它们同时移动,问相聚时的最小花费. 然后是m个点集,点集内的任意两点之间的移动花费为tisolve:因为是同时移动. 所以分别对1和n求一个最短路. 然后每个节点取两个最短路中的最大值就能得到花费.最开始想的是建立所有边,但是边的数量会太多.所有走到一个节点时,将其所在的所有点集处理一遍. 而且只需要处理一次即可,已经维护了一个最短状态.hhh-2016-08-30 19:56:48*/#pragma comment(linker,"/STACK:124000000,124000000")#include <algorithm>#include <iostream>#include <cstdlib>#include <cstdio>#include <cstring>#include <vector>#include <math.h>#include <queue>#include <set>#include <map>#define lson  i<<1#define rson  i<<1|1#define ll long long#define clr(a,b) memset(a,b,sizeof(a))#define scanfi(a) scanf("%d",&a)#define scanfs(a) scanf("%s",a)#define scanfl(a) scanf("%I64d",&a)#define key_val ch[ch[root][1]][0]#define inf 0x3f3f3f3f3f3f3f3fusing namespace std;const ll mod = 1e9+7;const int maxn = 100010;struct qnode{    int v,c;    qnode(int _v = 0 ,int _c =0) : v(_v),c(_c){}    bool operator <(const qnode &a)const    {        return c > a.c;    }};bool vis[maxn];bool tvis[maxn];ll dis1[maxn], dis2[maxn],cost[maxn];int anspos[maxn];int num[maxn];vector<int> pos[maxn];vector<int> have[maxn];int T,n,m;void dijkstra(int start,ll dis[]){    for(int i= 1;i <= n;i++)    {        vis[i] = tvis[i] = 0;        dis[i] = inf;    }    priority_queue<qnode> q;    q.push(qnode(start,0));    dis[start] = 0;    qnode t;    while(!q.empty())    {        t = q.top();        q.pop();        int u = t.v;        if(vis[u]) continue;        vis[u] = 1;        for(int i = 0 ;i < pos[u].size();i++)        {            int t = pos[u][i];//            if(tvis[t]) continue;//            tvis[t] = 1;            for(int j = 0;j<have[t].size();j++)            {                int v = have[t][j];                if(v == u)                    continue;                if(dis[v] > dis[u] + cost[t])                {                    dis[v] = dis[u] + cost[t];                    q.push(qnode(v,dis[v]));                }            }        }    }}int main(){    int x;//    freopen("in.txt","r",stdin);    scanfi(T);    int cas = 1;    while(T--)    {        scanfi(n),scanfi(m);        for(int i = 0 ;i <= n;i++)           pos[i].clear();        for(int i = 0;i <= m;i++)            have[i].clear();        for(int i = 1;i <= m;i++)        {            scanf("%I64d%d",&cost[i],&num[i]);            for(int j = 0;j < num[i];j++)            {                scanfi(x);                pos[x].push_back(i);                have[i].push_back(x);            }        }        dijkstra(1,dis1);        dijkstra(n,dis2);        int cnt = 0;        ll ans = inf;        for(int i = 1;i <= n;i++)        {            ll t = max(dis1[i],dis2[i]);            if(t != inf){                ans = min(ans,t);            }        }        for(int i =1; i <= n;i++)        {            if(max(dis1[i],dis2[i]) == ans)            anspos[cnt++] = i;        }        printf("Case #%d: ",cas++);       if(ans != inf)       {           printf("%I64d\n",ans);           for(int i = 0;i < cnt;i++)           {               printf("%d%c",anspos[i],i == cnt-1 ? ‘\n‘:‘ ‘);           }       }       else        printf("Evil John\n");    }    return 0;}