題目鏈接：https://www.luogu.org/problem/P4568

不管是k條免費還是半價都可以做~~~

兩種方法：

1.分層建圖（但這種方法建圖復(fù)雜度有點大）

就是幾條免費建層圖，每一層都有對應(yīng)關(guān)系，層與層之間是也是對應(yīng)關(guān)系但是價格免費

大概就是這么個意思，分層是常用的思路，k比較小才可以這樣，不然會爆掉

?

//#pragma comment (linker, "/STACK:102400000,102400000")
#include<bits/stdc++.h>
#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#include<list>
#include<time.h>
#include<bitset>#define myself i,l,r
#define lson i<<1
#define rson i<<1|1
#define Lson i<<1,l,mid
#define Rson i<<1|1,mid+1,r
#define half (l+r)/2
#define lowbit(x) x&(-x)
#define min4(a, b, c, d) min(min(a,b),min(c,d))
#define min3(x, y, z) min(min(x,y),z)
#define max3(x, y, z) max(max(x,y),z)
#define max4(a, b, c, d) max(max(a,b),max(c,d))
#define pii make_pair
#define pr pair<int,int>
typedef unsigned long long ull;
typedef long long ll;
const int inff = 0x3f3f3f3f;
const long long inFF = 9223372036854775807;
const int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
const int mdir[8][2] = {0, 1, 0, -1, 1, 0, -1, 0, 1, 1, -1, 1, 1, -1, -1, -1};
const double eps = 1e-10;
const double PI = acos(-1.0);
const double E = 2.718281828459;
using namespace std;
const int mod=1e9+7;
const int maxn=110005;
const int maxm=1200005;
int d[maxn];
int head[maxn],sign;
int n,m,k;
struct node
{int to,p,val;
}edge[maxm<<1];
void add(int u,int v,int val)
{edge[sign]=node{v,head[u],val};head[u]=sign++;
}
void addedge(int u,int v,int val)
{add(u,v,val),add(v,u,val);for(int i=1;i<=k;i++){add(u+i*n,v+i*n,val);add(v+i*n,u+i*n,val);add(u+(i-1)*n,v+i*n,0);add(v+(i-1)*n,u+i*n,0);}
}
void init()
{sign=0;memset(head,-1,sizeof(head));
}
void dij(int st)
{memset(d,0x3f,sizeof(d));d[st]=0;priority_queue<pr,vector<pr>,greater<pr> > q;q.push(pii(0,st));while(!q.empty()){pr now=q.top();q.pop();if(d[now.second]<now.first) continue;for(int i=head[now.second];~i;i=edge[i].p){int v=edge[i].to;if(d[v]>d[now.second]+edge[i].val){d[v]=d[now.second]+edge[i].val;q.push(pii(d[v],v));}}}
}
int main()
{int st,ed,x,y,val;scanf("%d %d %d",&n,&m,&k);init();scanf("%d %d",&st,&ed);for(int i=1;i<=m;i++){scanf("%d %d %d",&x,&y,&val);addedge(x,y,val);}for(int i=1;i<=k;i++)add(ed+(i-1)*n,ed+i*n,0);dij(st);printf("%d\n",d[ed+n*k]);return 0;
}

2.就是開二維數(shù)組dp

d[i][cnt]表示從st到i點用了cnt次免費的距離

每次松弛的時候判斷一下u-v能不能用免費，能用免費d[v][cnt+1]=d[u][cnt]

不能用免費的話就是正常的判斷 d[v][cnt]>d[u][cnt]+len(u,v) ?

思路就是這樣，終于學(xué)了這個板子，我以為好難

//#pragma comment (linker, "/STACK:102400000,102400000")
#include<bits/stdc++.h>
#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#include<list>
#include<time.h>
#include<bitset>#define myself i,l,r
#define lson i<<1
#define rson i<<1|1
#define Lson i<<1,l,mid
#define Rson i<<1|1,mid+1,r
#define half (l+r)/2
#define lowbit(x) x&(-x)
#define min4(a, b, c, d) min(min(a,b),min(c,d))
#define min3(x, y, z) min(min(x,y),z)
#define max3(x, y, z) max(max(x,y),z)
#define max4(a, b, c, d) max(max(a,b),max(c,d))
#define pii make_pair
#define pr pair<int,int>
typedef unsigned long long ull;
typedef long long ll;
const int inff = 0x3f3f3f3f;
const long long inFF = 9223372036854775807;
const int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
const int mdir[8][2] = {0, 1, 0, -1, 1, 0, -1, 0, 1, 1, -1, 1, 1, -1, -1, -1};
const double eps = 1e-10;
const double PI = acos(-1.0);
const double E = 2.718281828459;
using namespace std;
const int mod=1e9+7;
const int maxn=1e4+5;
const int maxm=1e5+5;
int d[maxn][11],vis[maxn][11];
int head[maxn],sign;
int n,m,k;
struct nod
{int u,val,t;bool friend operator<(nod s,nod e){return s.val>e.val;}
};
struct node
{int to,p,val;
}edge[maxm<<1];
void add(int u,int v,int  val)
{edge[sign]=node{v,head[u],val};head[u]=sign++;
}
void init()
{sign=0;for(int i=0;i<=n;i++) head[i]=-1;
}
int dij(int st,int ed)
{for(int i=0;i<=n;i++)for(int j=0;j<=k;j++)d[i][j]=inff,vis[i][0]=0;d[st][0]=0;priority_queue<nod> q;q.push(nod{st,0,0});while(!q.empty()){nod now=q.top();q.pop();int u=now.u,t=now.t;if(vis[u][t]) continue;vis[u][t]=1;if(u==ed) return d[u][t];for(int i=head[u];~i;i=edge[i].p){int v=edge[i].to;if(t<k&&d[v][t+1]>d[u][t]){d[v][t+1]=d[u][t];q.push(nod{v,d[v][t+1],t+1});}if(d[v][t]>d[u][t]+edge[i].val){d[v][t]=d[u][t]+edge[i].val;q.push(nod{v,d[v][t],t});}}}return -1;
}
int main()
{int st,ed,x,y,val;scanf("%d %d %d",&n,&m,&k);init();scanf("%d %d",&st,&ed);for(int i=1;i<=m;i++){scanf("%d %d %d",&x,&y,&val);add(x,y,val),add(y,x,val);}printf("%d\n",dij(st,ed));return 0;
}

?

總結(jié)

以上是生活随笔為你收集整理的洛谷P4568 飞行路线 最短路k条免费的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。