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

· · 题解

下面的做法虽然能通过此题数据，但其实是错误的。请有兴趣的读者自行研究该算法的错误在哪里。

标算是跑四趟SPFA，然后拓扑排序求最长链。

这里介绍一种Dijkstra的做法：

对于两个起点、终点分别跑一个Dijkstra，然后枚举每个点对，判断是否都在最短路上，并对其距离取max。

BZOJ上跑了440ms，内存6556KB，代码长度1906B，比标算不知强到哪里去了。

#include<cstdio>
#include<cctype>
#include<functional>
#include<ext/pb_ds/priority_queue.hpp>
inline int getint() {
    char ch;
    while(!isdigit(ch=getchar()));
    int x=ch^'0';
    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
    return x;
}
const int inf=0x7fffffff;
const int V=1501;
struct Edge {
    int to,w;
};
std::vector<Edge> e[V];
inline void add_edge(const int u,const int v,const int w) {
    e[u].push_back((Edge){v,w});
}
struct Vertex {
    int id,dis;
    bool operator > (const Vertex &another) const {
        return dis>another.dis;
    }
};
int n,s1,t1,s2,t2;
int ds1[V],dt1[V],ds2[V],dt2[V];
__gnu_pbds::priority_queue<Vertex,std::greater<Vertex> > q;
__gnu_pbds::priority_queue<Vertex,std::greater<Vertex> >::point_iterator p[V];
inline void Dijkstra(const int s,int *dis) {
    q.clear();
    for(int i=1;i<=n;i++) {
        p[i]=q.push((Vertex){i,dis[i]=(i==s?0:inf)});
    }
    while(q.top().dis!=inf) {
        int x=q.top().id;
        for(unsigned i=0;i<e[x].size();i++) {
            Edge &y=e[x][i];
            if(dis[x]+y.w<dis[y.to]) {
                q.modify(p[y.to],(Vertex){y.to,dis[y.to]=dis[x]+y.w});
            }
        }
        q.modify(p[x],(Vertex){x,inf});
    }
}
inline bool check(const int x) {
    return (ds1[x]+dt1[x]==ds1[t1])&&(ds2[x]+dt2[x]==ds2[t2]);
}
int main() {
    n=getint();
    int m=getint();
    s1=getint(),t1=getint(),s2=getint(),t2=getint();
    for(int i=0;i<m;i++) {
        int u=getint(),v=getint(),w=getint();
        add_edge(u,v,w);
        add_edge(v,u,w);
    }
    Dijkstra(s1,ds1);
    Dijkstra(t1,dt1);
    Dijkstra(s2,ds2);
    Dijkstra(t2,dt2);
    int ans=0;
    for(int i=1;i<=n;i++) {
        if(!check(i)) continue;
        for(int j=i+1;j<=n;j++) {
            if(!check(j)) continue;
            ans=std::max(ans,std::abs(ds1[i]-ds1[j]));
        }
    }
    printf("%d\n",ans);
    return 0;
}