hdu-5521-Meeting-最短路-増点建図

http://acm.hdu.edu.cn/showproblem.php?pid=5521
タイトルの意味はあなたに1つの図をあげて、nの都市、1とnの出会う最も短い距離を求めて、明らかにそれぞれ1とnで出発して1回の最も短い距離を求めて、答えはmin【max(dis 1[i],disn[i])】です
...しかし、本題で与えられた図は特別で、m個の集合を直接与え、各集合にはk個の点があり、集合内の任意の2点の間の辺権はtである.
明らかに暴力的にn^2建図することはできません.そうしないと極端な状況が掛かります.
私たちは1つの 存在しないノードで図を作成するには、次の手順に従います.
各集合newに対して1つの点n+iは,集合内のすべての点を連通し,tとする.
これにより,集合内のすべての点が連通するが,実際に計算された辺権は2 tにすぎない.大丈夫です.私たちは直接答えを出力するときに答えを2つ除けばいいです.
これにより、図の最大ノードはn*2となり、残りは通常の最短回路と変わらないでしょう.
2 S走った

//poj2387  -- n 1   
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <vector>
using namespace std;
struct node
{
    int x,v;
    node() {}
    node(int a,int b)
    {
        x=a;
        v=b;
    }
    bool operator <(const node&b) const
    {
        return v>b.v;					//*****
    }
};
vector<node> mp[200050];

int dist1[200005];
int dist2[200005];     //n        
const int inf=2147483647;
priority_queue<node> qq;
int st;
int n,m;
int main()
{
    int t;
    cin>>t;
    void dji(int []);
    int cnt=1;
    while(t--)
    {
        int i,j;
        int a,b,c;
        cin>>n>>m;
        for (i=1; i<=2*n; i++) mp[i].clear();

        int idx=n;
        for (i=1; i<=m; i++)
        {
            idx++;
            int tt,kk,x;
            scanf("%d%d",&tt,&kk);

            for (j=1; j<=kk; j++)
            {
                scanf("%d",&x);
                mp[idx].push_back(node(x,tt));
                mp[x].push_back(node(idx,tt));
            }
        }
        int tmpn=n;
        n=idx;

        st=1;
        dji(dist1);
        st=tmpn;
        dji(dist2);
        int minn=inf;
        printf("Case #%d: ",cnt++);
        // for (i=1;i<=tmpn;i++) dist1[i]/=2,dist2[i]/=2;

        for (i=1; i<=tmpn; i++)
        {
            minn=min(minn,max(dist1[i],dist2[i]));
        }
        if (dist1[tmpn]==inf)
            printf("Evil John
");
        else
        {
            printf("%d
",minn/2);  //       
            int line=0;
            for (i=1; i<=tmpn; i++)
            {
                if(max(dist1[i],dist2[i])==minn)
                {

                    if (line)  printf(" ");
                    printf("%d",i);
                    line=1;
                }
            }
            printf("
");
        }
    }
    return 0;
}

void dji(int dist[])
{
    while(!qq.empty())  qq.pop();
    int i;
    int vis[200005];
    for (i=1; i<=n; i++)
    {
        dist[i]=inf;
        vis[i]=0;
    }
    dist[st]=0;
    node sst(st,0);
    qq.push(sst);

    while(!qq.empty())
    {
        node t=qq.top();
        qq.pop();
        int num=t.x;
        if (vis[num]) continue;
        vis[num]=1;
        for (i=0; i<mp[num].size(); i++)
        {
            node tmp=mp[num][i];
            int x=tmp.x;
            int v=tmp.v;

            if (!vis[x]&&v+dist[num]<dist[x])
            {
                dist[x]=v+dist[num];
                node np(x,dist[x]);
                qq.push(np);
            }
        }
    }

}