BZOJ

分析

好像是好久以前讲课的题...

暴力建图就是把边看成点,然而边数是 $\mathcal{O}(m^2)$ 级别的。

我们把每条边拆成两条,分别表示两个端点的出边。

考虑到 $\max\left\{a,b\right\}=a+\max\left\{b-a,0\right\}$。因此我们对于每个点 $u$,将与它相连的所有出边按边权从小到大排序,然后其中第 $i$ 条向第 $i+1$ 条连边权为 $w_{i+1}-w_i$ 的边,第 $i+1$ 条向第 $i$ 条连边权为 $0$ 的边。另外对于每条出边 $i$,要从它对应的入边 $i'$ 向它连边权为 $w_i$ 的边。

然后,新建一个源点 $s$ 和汇点 $t$,从 $s$ 向 $1$ 的所有出边连边权为 $w$ 的边,从 $n$ 的所有入边向 $t$ 连边权为 $w$ 的边。

可以发现这样子建图还是对的,那么只需要跑一遍最短路就好了。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#define re register
using namespace std;
typedef long long ll;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10,V=400000+10,E=2000000+10;

int n,m,s,t;
struct sedge { int v,w,id; };
bool operator <(sedge a,sedge b) { return a.w<b.w; }
vector<sedge> G[N];

struct edge { int v,w,nxt; } e[E];
int head[V];
inline void addEdge(int u,int v,int w) {
    static int cnt=0;
    e[++cnt]=(edge){v,w,head[u]},head[u]=cnt;
}

struct node { int u; ll d; };
bool operator <(node a,node b) { return a.d>b.d; }
ll dis[V];
inline void dijkstra() {
    memset(dis,0x3f,sizeof(dis)),dis[s]=0;
    priority_queue<node> Q; Q.push((node){s,0});
    while (!Q.empty()) {
        int u=Q.top().u; ll d=Q.top().d; Q.pop();
        if (dis[u]!=d) continue;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v,w=e[i].w;
            if (dis[u]+w<dis[v])
                dis[v]=dis[u]+w,Q.push((node){v,dis[v]});
        }
    }
}

int main() {
    n=read(),m=read(),s=0,t=1;
    for (re int i=1;i<=m;++i) {
        int u=read(),v=read(),w=read();
        G[u].push_back((sedge){v,w,i<<1});
        G[v].push_back((sedge){u,w,i<<1|1});
    }
    for (re int i=1;i<=n;++i) {
        sort(G[i].begin(),G[i].end());
        for (re int j=0;j<G[i].size();++j) {
            addEdge(G[i][j].id^1,G[i][j].id,G[i][j].w);
            if (i==1) addEdge(s,G[i][j].id,G[i][j].w);
            if (G[i][j].v==n) addEdge(G[i][j].id,t,G[i][j].w);
        }
        for (re int j=1;j<G[i].size();++j) {
            addEdge(G[i][j-1].id,G[i][j].id,G[i][j].w-G[i][j-1].w);
            addEdge(G[i][j].id,G[i][j-1].id,0);
        }
    }
    dijkstra(); printf("%lld\n",dis[t]);
    return 0;
}
最后修改:2019 年 11 月 14 日 08 : 31 PM