LOJ2350：[JOI2017/2018决赛]月票购买——题解

比较简单的题，为什么我实现得这么sb？

第一个包其实已经给了提示（第一个包的解法就是在S->T所有最短路径上的所有点到V的最短路的最小值。）

那么我们先把所有最短路径存成新的图，然后dfs每一条路径，然后找到路径上两个点(i,j)，构成一条U->i->j->V，把所有这样的路的答案更新即为所求。

然后就是代码实现的问题了，dfs肯定不行，那么考虑开两个数组f[i]和t[i]表示i往后的路径点j中，U->j最小值和j->V最小值。

那么答案就是min(U->i+t[i],f[i]+i->V)。

也就是说我们需要从T往S推f[i]和t[i]，那么就一遍dfs，最后再将当前点加入队列，则点顺序正好满足推的过程。

#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;
typedef long long ll;
typedef pair<ll,int>pii;
typedef __gnu_pbds::priority_queue<pii,greater<pii>,__gnu_pbds::pairing_heap_tag> heap;
#define fi first
#define se second
const int N=1e5+5;
const int M=2e5+5;
const ll INF=1e18;
inline int read(){
    int X=0,w=0;char ch=0;
    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
    while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}
struct node{
    int cnt,head[N];
    int w[M*2],to[M*2],nxt[M*2];
    node(){
    cnt=0;memset(head,0,sizeof(head));
    }
    inline void add(int u,int v,int k){
    to[++cnt]=v;w[cnt]=k;nxt[cnt]=head[u];head[u]=cnt;
    }
}e,f;
int n,m,S,T,U,V;
ll dis[4][N];
heap q;
heap::point_iterator id[N];
void dij(int s,int on){
    for(int i=1;i<=n;i++)dis[on][i]=INF,id[i]=0;
    dis[on][s]=0;id[s]=q.push(pii(0,s));
    while(!q.empty()){
    int u=q.top().se;q.pop();
    for(int i=e.head[u];i;i=e.nxt[i]){
        int v=e.to[i],w=e.w[i];
        if(dis[on][v]>dis[on][u]+w){
        dis[on][v]=dis[on][u]+w;
        if(id[v]!=0)q.modify(id[v],pii(dis[on][v],v));
        else id[v]=q.push(pii(dis[on][v],v));
        }
    }
    }
    return;
}
bool vis[N];
ll ans,mint[N],minf[N];
int dui[N],r;
inline int turn(int i){if(i&1)return i+1;return i-1;}
void dfs(int u){
    vis[u]=1;
    for(int i=f.head[u];i;i=f.nxt[i]){
    int v=f.to[i];
    if(!vis[v])dfs(v);
    }
    dui[++r]=u;
}
int main(){
    n=read(),m=read();
    S=read(),T=read(),U=read(),V=read();
    for(int i=1;i<=m;i++){
    int u=read(),v=read(),w=read();
    e.add(u,v,w);e.add(v,u,w);
    }
    dij(S,0);dij(T,1);dij(U,2);dij(V,3);
    for(int i=1;i<=e.cnt;i++){
    int u=e.to[turn(i)],v=e.to[i],w=e.w[i];
    if(dis[0][u]+w+dis[1][v]==dis[0][T])f.add(u,v,0);
    }
    ans=dis[2][V];dfs(S);
    for(int i=1;i<=r;i++){
    int u=dui[i];
    minf[u]=dis[2][u],mint[u]=dis[3][u];
    for(int j=f.head[u];j;j=f.nxt[j]){
        int v=f.to[j];
        minf[u]=min(minf[v],minf[u]);
        mint[u]=min(mint[v],mint[u]);
    }
    ans=min(ans,min(minf[u]+dis[3][u],dis[2][u]+mint[u]));
    }
    printf("%lld
",ans);
    return 0;
}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。　　　　　　　　　　　　　　+

+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++

LOJ2350：[JOI2017/2018决赛]月票购买——题解

相关推荐