BZOJ4289:[PA2012]Tax（Dijkstra）_给定一张有n个点的m条边的无向图,其中第i条边的花费是2^i。问从某一点出发,遍历完

传送门

给出一个N个点M条边的无向图，经过一个点的代价是进入和离开这个点的两条边的边权的较大值，求从起点1到点N的最小代价。起点的代价是离开起点的边的边权，终点的代价是进入终点的边的边权。$(n\le 100000,m \le 200000)$

题解：Dijkstra

首先暴力就是把每个点的状态加上是从哪一条边进入的，即是把每条边看做一个点，这样虽然点数是$O(n)$的，但边数是$O(m^2)$(当然不是要你真的把边建出来)，跑最大数据大概要1.8s.

Code:http://paste.ubuntu.com/25916470/

考虑优化边数。因为一个点的很多边彼此之间有着联系，每两个都连边有点浪费。发现其实一个边进入一个点之后对于所有比他小的边长度都是他自己，比他大的边增长的值为两边的差值，优化已经很明显：对于一个点，先把出入边按权值排序，入边连向他的反向边，每个反向边往下连长度为0的边，向上连长度为两边差值的边，边数也优化到了$O(m)$。时间复杂度$O(m\log m)$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int> pii;
inline int read(){
    char ch=getchar();int i=0,f=1;
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){i=(i<<1)+(i<<3)+ch-'0';ch=getchar();}
    return i*f;
}
const int Maxn=1e5+50,Maxm=4e5+50;
int n,m,nxt[Maxm],to[Maxm],val[Maxm],last[Maxn],ecnt=1,vis[Maxm],tot;
vector<pii>edge[Maxm];
struct E{
    int id,val;
    E(){}
    E(int x,int z):id(x),val(z){} 
    friend inline bool operator <(const E &a,const E &b){
        return a.val<b.val;
    }
}que[Maxm];
long long dis[Maxm];
inline void add(int x,int y,int w){
    nxt[++ecnt]=last[x];last[x]=ecnt;to[ecnt]=y;val[ecnt]=w;
}
priority_queue< pii,vector<pii>,greater<pii> >q;
inline void dij(){
    memset(dis,0x3f,sizeof(dis));
    for(int e=last[1];e;e=nxt[e]){
        dis[e]=val[e];q.push(make_pair(dis[e],e));
    }
    while(!q.empty()){
        if(vis[q.top().second]){q.pop();continue;}
        int u=q.top().second;q.pop();vis[u]=1;
        for(int e=edge[u].size()-1;e>=0;e--){ 
            int v=edge[u][e].first,w=edge[u][e].second;
            if(vis[v])continue;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                q.push(make_pair(dis[v],v));
            }
        }
    }
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=m;i++){
        int x=read(),y=read(),w=read();
        add(x,y,w);add(y,x,w);
    }
    for(int i=2,tp=0;i<n;tp=0,i++){
        for(int e=last[i];e;e=nxt[e])
            que[++tp]=E(e,val[e]);
        sort(que+1,que+tp+1);
        for(int j=1;j<=tp;j++){
            if(j!=1)edge[que[j].id].push_back(make_pair(que[j-1].id,0));
            if(j!=tp)edge[que[j].id].push_back(make_pair(que[j+1].id,que[j+1].val-que[j].val));
            edge[que[j].id^1].push_back(make_pair(que[j].id,que[j].val));
        }
    }
    dij();
    long long ans=0x3f3f3f3f3f3f3f3f;
    for(int e=last[n];e;e=nxt[e]){
        ans=min(ans,dis[e^1]+val[e]);
    }
    cout<<ans<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67