题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2763
分层图两种方法的练习。
1.把图分成k+1层，本层去上面一层的边免费。但空间时间都不算优秀。
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #define ll long long using namespace std; const int N=1e4+5,M=5e4+5,K=15; int n,m,k,head[N*K],xnt,s,t; ll dis[N*K],ans=0x7fffffff; bool vis[N*K]; struct Edge{ int next,to,w; Edge(int n=0,int t=0,int w=0):next(n),to(t),w(w) {} }edge[M*K<<2]; void add(int x,int y,int z) { for(int fx=0;fx<=k*n;fx+=n) { edge[++xnt]=Edge(head[x+fx],y+fx,z);head[x+fx]=xnt; if(fx<k*n) edge[++xnt]=Edge(head[x+fx],y+fx+n,0),head[x+fx]=xnt; } } void dj() { memset(dis,1,sizeof dis);dis[s]=0; priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > > q; q.push(make_pair(0,s)); while(q.size()) { int u=q.top().second;q.pop(); while(vis[u]&&q.size())u=q.top().second,q.pop(); if(vis[u])break;vis[u]=1; for(int i=head[u],v;i;i=edge[i].next) if(dis[v=edge[i].to]>dis[u]+edge[i].w) { dis[v]=dis[u]+edge[i].w;q.push(make_pair(dis[v],v)); } } } int main() { scanf("%d%d%d%d%d",&n,&m,&k,&s,&t); int x,y,z; for(int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&z); add(x,y,z);add(y,x,z); } dj(); for(int fx=0;fx<=k*n;fx+=n)ans=min(ans,dis[t+fx]); printf("%lld",ans); return 0; }
2.设计dp状态，套在最短路上。就不用建边，从而省空间。
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #define ll long long using namespace std; const int N=1e4+5,M=5e4+5,K=15; int n,m,k,s,t,head[N],xnt; ll ans=0x7fffffff,dp[N][K]; bool vis[N][K]; struct Edge{ int next,to,w; Edge(int n=0,int t=0,int w=0):next(n),to(t),w(w) {} }edge[M<<1]; void add(int x,int y,int z) { edge[++xnt]=Edge(head[x],y,z);head[x]=xnt; edge[++xnt]=Edge(head[y],x,z);head[y]=xnt; } void spfa() { memset(dp,1,sizeof dp);dp[s][0]=0; queue<pair<int,int> > q;q.push(make_pair(s,0));vis[s][0]=1; while(q.size()) { int u=q.front().first,d=q.front().second;q.pop(); vis[u][d]=0; for(int i=head[u],v;i;i=edge[i].next) { if(dp[v=edge[i].to][d]>dp[u][d]+edge[i].w) { dp[v][d]=dp[u][d]+edge[i].w; if(!vis[v][d])vis[v][d]=1,q.push(make_pair(v,d)); } if(d<k&&dp[v][d+1]>dp[u][d]) { dp[v][d+1]=dp[u][d]; if(!vis[v][d+1])vis[v][d+1]=1,q.push(make_pair(v,d+1)); } } } } int main() { scanf("%d%d%d%d%d",&n,&m,&k,&s,&t); int x,y,z; for(int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&z);add(x,y,z); } spfa(); for(int i=0;i<=k;i++)ans=min(ans,dp[t][i]); printf("%lld",ans); return 0; }
上面的代码巨慢！用dj的话可以及时推出，所以会非常快！
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #define ll long long using namespace std; const int N=1e4+5,M=5e4+5,K=15; int n,m,k,s,t,head[N],xnt; ll ans=0x7fffffff,dp[N][K]; bool vis[N][K]; struct Edge{ int next,to,w; Edge(int n=0,int t=0,int w=0):next(n),to(t),w(w) {} }edge[M<<1]; struct Node{ ll dis;int v,c; Node(ll d,int a,int b):dis(d),v(a),c(b) {} bool operator<(const Node k)const { return dis>k.dis; } }; void add(int x,int y,int z) { edge[++xnt]=Edge(head[x],y,z);head[x]=xnt; edge[++xnt]=Edge(head[y],x,z);head[y]=xnt; } void dj() { memset(dp,1,sizeof dp);dp[s][0]=0; priority_queue<Node> q; q.push(Node(0,s,0)); while(q.size()) { ll x=q.top().dis,u=q.top().v,d=q.top().c;q.pop(); while(vis[u][d]&&q.size())x=q.top().dis,u=q.top().v,d=q.top().c,q.pop(); if(vis[u][d])break;vis[u][d]=1; if(u==t){ans=x;return;} for(int i=head[u],v;i;i=edge[i].next) { if(dp[v=edge[i].to][d]>x+edge[i].w) { dp[v][d]=x+edge[i].w;q.push(Node(dp[v][d],v,d)); } if(d<k&&dp[v][d+1]>x) { dp[v][d+1]=x;q.push(Node(dp[v][d+1],v,d+1)); } } } } int main() { scanf("%d%d%d%d%d",&n,&m,&k,&s,&t); int x,y,z; for(int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&z);add(x,y,z); } dj(); printf("%lld",ans); return 0; }