HDU-5521 Meeting （最短路）

题目大意

给标记从1-n的节点，并且进行了分块（分块可能会有重合），第i个分块内部有$s_i$si​个节点，节点两两之间都有路径相连，通过的时间都是$t_i$ti​。现在一头奶牛从节点1出发，另一头从n出发，想找一个中间的节点开会，想找一个节点使得路上花费的时间最小。

思路

很显然一个最短路的问题。从1点跑一个最短路，从n点跑一个最短路，每一个节点都算一个开会时间，然后取最短就行。而一个节点的开会时间一定是两头牛中来得慢的那头的路上花费时间（同时出发，来得早的可以等他的同伴）。问题其实有两个。

首先是建图的问题。如果用普通的邻接表或者邻接矩阵抑或是链式前向星，分块都是完全图/团，所以建图的时间是$O(n^2)$O(n2)，肯定要T。所以我队队宝阿忠哥想出来一个“阿忠图”的建图方式，就是把所有的团内部的节点放进一个集合，并把每个集合标记上自己所在的团的编号，每次最短路松弛的时候就遍历所有自己有在的团，具体就是：

vector<long long> es[1000005];//标记每个团内有哪些节点
vector<long long> inque[100005];//标记每个节点在哪些团内
/*
*以下省略N行代码
*/
	for(long long i=1; i<=m; i++)
    {
        es[i].clear();//清空第i个团
        long long s;
        scanf("%lld%lld",&t[i],&s);
        for(long long j=0; j<s; j++)
        {
            long long temp;
            scanf("%lld",&temp);
            inque[temp].push_back(i);//标记temp节点所在的团有i
            es[i].push_back(temp);//标记i团内有temp节点
        }
    }

建图时间就是$O(n)$O(n)。

第二个问题就是因为团内节点两两之间都有相同权值的边，所以团内节点松弛没有意义，所以每次Dijkstra，每个团都只需要遍历一次。

这个地方是最难想的，我们队在打这场2015 ICPC沈阳站的重现赛的时候，什么都想到了，以为我的代码写丑了阿忠哥帮我重写了，输入输出换成scanf和printf了，甚至各种STL都替换成手写版本了，阿忠哥已经把优先队列换成手写小顶堆了，仁至义尽，无力回天，T了整整$(1000)_B$(1000)B​发！！！（根本不是卡常啊喂！被卡常卡怕了的我队日常）反正赛后搜了题解，秒懂。。。然后把我的丑陋STL依赖代码改了两行代码秒过。

具体实现就是加一个bool型vis数组，每次遍历完一个团就标记了，下次不许遍历这个团了：

		for(long long i=0; i<inque[now.second].size(); i++)
        {
            long long nxtedge=inque[now.second][i];
            if(vis[nxtedge])
            {
                continue;//遍历过了不许遍历了
            }
            vis[nxtedge]=true;//该团遍历过了标记一个
            for(long long j=0; j<es[nxtedge].size(); j++)
            {
                long long nxt=es[nxtedge][j];
                if(nxt!=now.second && dis[nxt]>dis[now.second]+t[nxtedge])
                {
                    dis[nxt]=dis[now.second]+t[nxtedge];
                    qq.push(make_pair(dis[nxt],nxt));
                }
            }
        }

加了这个优化，写的最丑的依赖STL我的代码都过了

代码

#include <bits/stdc++.h>
using namespace std;
vector<long long> inque[100005];
vector<long long> es[1000005];
vector<long long> ans;
long long t[1000005];
long long dis[100005];
long long dis2[100005];
long long n,m;
bool vis[1000005];
void dij(long long s)//其实这里传一个数组参就可以了，我复制了一份。。。
{
    memset(dis,0x3f,sizeof(dis[0])*(n+1));
    memset(vis,0,sizeof(vis[0])*(n+1));
    dis[s]=0;
    priority_queue<pair<long long,long long>,vector<pair<long long,long long> >,greater<pair<long long,long long> > > qq;
    qq.push(make_pair(dis[s],s));
    while(!qq.empty())
    {
        pair<long long,long long> now = qq.top();
        qq.pop();
        if(now.first>dis[now.second])
        {
            continue;
        }
        for(long long i=0; i<inque[now.second].size(); i++)
        {
            long long nxtedge=inque[now.second][i];
            if(vis[nxtedge])
            {
                continue;
            }
            vis[nxtedge]=true;
            for(long long j=0; j<es[nxtedge].size(); j++)
            {
                long long nxt=es[nxtedge][j];
                if(nxt!=now.second && dis[nxt]>dis[now.second]+t[nxtedge])
                {
                    dis[nxt]=dis[now.second]+t[nxtedge];
                    qq.push(make_pair(dis[nxt],nxt));
                }
            }
        }
    }
}
void dij2(long long s)
{
    memset(dis2,0x3f,sizeof(dis2[0])*(n+1));
    memset(vis,0,sizeof(vis[0])*(n+1));
    dis2[s]=0;
    priority_queue<pair<long long,long long>,vector<pair<long long,long long> >,greater<pair<long long,long long> > > qq;
    qq.push(make_pair(dis2[s],s));
    while(!qq.empty())
    {
        pair<long long,long long> now = qq.top();
        qq.pop();
        if(now.first>dis2[now.second])
        {
            continue;
        }
        for(long long i=0; i<inque[now.second].size(); i++)
        {
            long long nxtedge=inque[now.second][i];
            if(vis[nxtedge])
            {
                continue;
            }
            vis[nxtedge]=true;
            for(long long j=0; j<es[nxtedge].size(); j++)
            {
                long long nxt=es[nxtedge][j];
                if(nxt!=now.second && dis2[nxt]>dis2[now.second]+t[nxtedge])
                {
                    dis2[nxt]=dis2[now.second]+t[nxtedge];
                    qq.push(make_pair(dis2[nxt],nxt));
                }
            }
        }
    }
}
void solve()
{
    scanf("%lld%lld",&n,&m);
    for(long long i=1; i<=n; i++)
    {
        inque[i].clear();
    }
    for(long long i=1; i<=m; i++)
    {
        es[i].clear();
        long long s;
        scanf("%lld%lld",&t[i],&s);
        for(long long j=0; j<s; j++)
        {
            long long temp;
            scanf("%lld",&temp);
            inque[temp].push_back(i);
            es[i].push_back(temp);
        }
    }
    dij(1);
    dij2(n);
    long long miner=0x3f3f3f3f3f3f3f3f;
    for(long long i=1; i<=n; i++)
    {
        if(dis[i]<0x3f3f3f3f3f3f3f3f && dis2[i]<0x3f3f3f3f3f3f3f3f)
        {
            long long newer=max(dis[i],dis2[i]);
            miner=min(miner,newer);
        }
    }
    if(miner!=0x3f3f3f3f3f3f3f3f)
    {
        printf("%lld\n",miner);
        ans.clear();
        for(long long i=1; i<=n; i++)
        {
            if(dis[i]<0x3f3f3f3f3f3f3f3f && dis2[i]<0x3f3f3f3f3f3f3f3f)
            {
                long long newer=max(dis[i],dis2[i]);
                if(newer==miner)
                {
                    ans.push_back(i);
                }
            }
        }
        for(long long i=0; i<ans.size(); i++)
        {
            printf("%lld",ans[i]);
            if(i!=ans.size()-1)
            {
                printf(" ");
            }
            else
            {
                printf("\n");
            }
        }
    }
    else
    {
        printf("Evil John\n");
    }

}
int main()
{
    long long t;
    scanf("%lld",&t);
    for(long long caser=1; caser<=t; caser++)
    {
        printf("Case #%lld: ",caser);
        solve();
    }
    return 0;
}

参考了以下文章，表示感谢：

https://blog.csdn.net/alps233/article/details/51205385