题解 P2149 【[SDOI2009]Elaxia的路线】

木木！ · 2019-05-26 17:38:25 · 题解

蒟蒻的第一道紫题题解……最慢的做法（300+ms）

思路：首先跑四遍Dijkstra，选出所有满足dists1[a]+distt1[a]==dists1[t1] && dists2[a]+distt2[a]==dists2[t2]的点，即在双方最短路上都有的点。

可以看到，这些点构成了一些子图，这些子图的直径就是所求的长度。证明不会证。

求直径的方法就是随便选一个点，跑一遍Dijkstra，找到最远的那个点，再跑一遍Dijkstra，找到最远的距离，就是直径。（不会证）

时间复杂度：\Theta((n+m)logm + n^2)，循环里的Dijkstra可以被均摊掉，总花费不会大于一次整图的Dijkstra。

优化一下（在Dijkstra里面直接用队列记录访问过的点）可以做到\Theta((n+m)logm)，但是我懒……再说常数那么大，就算优化了也优化不了几ms。

用了一点函数指针知识以简化代码。

#include <queue>
#include <cstdio>
using namespace std;

void chkmax(int& a,int b)
{
    if(b>a)
    {
        a = b;
    }
}

int beg[1505];
int ed[450005];
int nxt[450005];
int len[450005];
int top;

void addedge(int a,int b,int l)
{
    ++top;
    len[top] = l;
    nxt[top] = beg[a];
    beg[a] = top;
    ed[top] = b;
}

int n;
int vis[1505];

void fillter_dijkstra(int* dist,int s,bool (*fillter)(int)) //fillter是个函数指针
{
    for(int i=1; i<=n; ++i)
    {
        dist[i] = 0x7f7f7f7f;
        vis[i] = 0;
    }
    dist[s] = 0;
    priority_queue<pair<int,int> > pq;
    pq.push(make_pair(0,s));

    while(!pq.empty())
    {
        int th = pq.top().second;
        pq.pop();
        while(vis[th])
        {
            if(pq.empty()) break;
            th = pq.top().second;
            pq.pop();
        }

        vis[th] = 1;

        for(int p=beg[th]; p; p=nxt[p])
        {
            if(fillter(ed[p]) && dist[th]+len[p] < dist[ed[p]])
            {
                dist[ed[p]] = dist[th]+len[p];
                pq.push(make_pair(-dist[ed[p]],ed[p]));
            }
        }
    }
}

bool always(int x)
{
    return true;
}

void dijkstra(int* dist,int s)
{
    fillter_dijkstra(dist,s,always);
}

int s1,t1,s2,t2;
int dists1[1505];
int dists2[1505];
int distt1[1505];
int distt2[1505];

bool can(int a)
{
    return dists1[a]+distt1[a]==dists1[t1] && dists2[a]+distt2[a]==dists2[t2];
}

int caned[1505];
int disttmp[1505];

int main()
{
    int m;
    scanf("%d%d%d%d%d%d",&n,&m,&s1,&t1,&s2,&t2);
    for(int i=1; i<=m; ++i)
    {
        int a,b,l;
        scanf("%d%d%d",&a,&b,&l);
        addedge(a,b,l);
        addedge(b,a,l);
    }

    dijkstra(dists1,s1);
    dijkstra(dists2,s2);
    dijkstra(distt1,t1);
    dijkstra(distt2,t2);

    int ans = 0;

    for(int i=1; i<=n; ++i)
    {
        if(!caned[i] && can(i))
        {
            fillter_dijkstra(disttmp,i,can);

            int maxpos = i;
            for(int j=1; j<=n; ++j)
            {
                if(vis[j])
                {
                    caned[j] = 1;
                    if(disttmp[j] > disttmp[maxpos])
                    {
                        maxpos = j;
                    }
                }
            }

            fillter_dijkstra(disttmp,maxpos,can);

            for(int j=1; j<=n; ++j)
            {
                if(vis[j])
                {
                    chkmax(ans,disttmp[j]);
                }
            }
        }
    }

    printf("%d\n",ans);
}