[BZOJ4398]福慧双修/[BZOJ2407]探险

题目大意：
　　给定一个$n(n\leq40000)$个点$m(m\leq100000)$条边的有向图，求从$1$出发回到$1$的不经过重复结点的最短路。

思路：
　　首先Dijkstra求出从1出发到每个结点$i$的单源最短路$dis[i]$及经过的第一个结点$first[i]$。
　　考虑重构图，将起点与终点区分开来，新建结点$n+1$表示终点。
　　枚举原图中的每一条边$(x,y,w)$，表示从$x$到$y$边权为$w$。
　　若$x=1,first[y]\ne y$，在新图中保留这条边；
　　若$y=1,first[x]\ne x$，说明存在一条从$1$沿最短路到$x$再到$1$的合法路径，在新图中连边$(1,n+1,w)$；
　　若$y=1,first[x]=x$，在新图中保留这条边；
　　若$x\ne1,y\ne1,first[x]\ne first[y]$，说明存在一条从$1$沿最短路到$x$再到$y$再沿最短路到$1$的合法路径，连边$(1,y,dis[x]+w)$;
　　若$x\ne1,y\ne1,first[x]=first[y]$，在新图中保留这条边。
　　最后再求一遍从$1$到$n+1$的最短路即可。

 #include<list>

 #include<cstdio>

 #include<cctype>

 #include<climits>

 #include<functional>

 #include<ext/pb_ds/priority_queue.hpp>

 inline int getint() {

     register char ch;

     while(!isdigit(ch=getchar()));

     register int x=ch^'';

     while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');

     return x;

 }

 const int N=;

 typedef std::pair<int,int> Edge;

 typedef std::list<Edge> List;

 typedef std::pair<int,int> Vertex;

 typedef __gnu_pbds::priority_queue<Vertex,std::greater<Vertex> > Heap;

 int n,dis[N],first[N];

 List e[N];

 inline void add_edge(const int &u,const int &v,const int &w) {

     e[u].push_front((Edge){v,w});

 }

 void dijkstra() {

     static Heap q;

     static Heap::point_iterator p[N];

     for(register int i=;i<=n;i++) {

         p[i]=q.push((Vertex){dis[i]=i==?:INT_MAX,i});

     }

     while(!q.empty()) {

         const int &x=q.top().second;

         for(register List::iterator i=e[x].begin();i!=e[x].end();i++) {

             const int &y=i->first,&w=i->second;

             if(dis[x]+w<dis[y]) {

                 first[y]=x==?y:first[x];

                 q.modify(p[y],(Vertex){dis[y]=dis[x]+w,y});

             }

         }

         q.pop();

     }

 }

 void rebuild() {

     n++;

     for(register int x=;x<=n;x++) {

         for(register List::iterator i=e[x].begin();i!=e[x].end();e[x].erase(i++)) {

             const int &y=i->first,&w=i->second;

             if(x==&&first[y]!=y) add_edge(,y,w);

             if(y==) first[x]==x?add_edge(x,n,w):add_edge(,n,dis[x]+w);

             if(x!=&&y!=) first[x]==first[y]?add_edge(x,y,w):add_edge(,y,dis[x]+w);

         }

     }

 }

 int main() {

     n=getint();

     for(register int m=getint();m;m--) {

         const int u=getint(),v=getint();

         add_edge(u,v,getint());

         add_edge(v,u,getint());

     }

     dijkstra();

     rebuild();

     dijkstra();

     printf("%d\n",dis[n]==INT_MAX?-:dis[n]);

     return ;

 }

巴特西

[BZOJ4398]福慧双修/[BZOJ2407]探险

最新文章

热门文章