bzoj2763[分层图]

发表于 | 分类于 | 阅读数 次

链接:bzoj2763[分层图]

题解

  • 分层图最短路，dis[i][j]表示到节点i用了j次免费的最小花费，更新的时候j<k的话尝试更新j+1次免费的最小花费，具体看代码。 
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
68
69
70
71
72
#include<iostream>
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
#define rep(i,x,y) for(register int i=x;i<=y;++i)
#define repd(i,x,y) for(register int i=x;i>=y;--i)
#define ll long long
using namespace std;
const int N=1e5+7;
template <typename T>inline void read(T &x){
    char c;int sign=1;x=0;
    do{c=getchar();if(c=='-')sign=-1;}while(c<'0'||c>'9');
    do{x=x*10+c-'0';c=getchar();}while(c>='0'&&c<='9');
    x*=sign;
}
int nxt[N],head[N],w[N],v[N],dis[N][13],vis[N][13];
int n,m,h,cnt,s,t;
inline void adde(int a,int b,int c){
    v[++cnt]=b;
    w[cnt]=c;
    nxt[cnt]=head[a];
    head[a]=cnt;
}
struct node{
    int d,u,id;
    node(int a=0,int b=0,int c=0):d(a),u(b),id(c){}
    bool operator<(const node &a)const {return d>a.d;}
};
priority_queue<node> q;
void dijkstra(){
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    q.push(node(0,s,0)); 
    while(!q.empty()){
        node a=q.top();
        q.pop();
        int ds=a.d,u=a.u,id=a.id;
        if(vis[u][id])continue;
        vis[u][id]=1;
        for(int i=head[u];i;i=nxt[i]){
            int k=v[i],c=w[i];
            if(id<h&&!vis[k][id+1]&&dis[k][id+1]>ds){
                dis[k][id+1]=ds;
                q.push(node(ds,k,id+1));
            }
            if(!vis[k][id]&&dis[k][id]>ds+c){
                dis[k][id]=ds+c;
                q.push(node(dis[k][id],k,id));
            }
        }
    }
}
int main(){
    read(n);read(m);read(h);
    read(s);read(t);
    rep(i,1,m){
        int a,b,c;
        read(a);read(b);read(c);
        adde(a,b,c);
        adde(b,a,c);
    }
    dijkstra();
    int ans=0x3f3f3f3f;
    rep(i,0,h)ans=min(ans,dis[t][i]);
    printf("%d\n",ans);
    return 0;
}