https://nanti.jisuanke.com/t/31001
题意 可以把k条边的权值变为0，求s到t的最短路
解析 分层最短路 我们建立k+1层图 层与层之间边权为0，i 向 i+1层转移，代表用了一条免费边。
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define fillchar(a, x) memset(a, x, sizeof(a))
#define huan printf("\n");
#define debug(a,b) cout<<a<<" "<<b<<" ";
using namespace std;
const int maxn=3e6+,inf=0x3f3f3f3f;
typedef long long ll;
typedef pair<int,int> pii;
int n,m,k,st,ed,cnt,head[maxn],vis[maxn];
ll dis[maxn];
struct node
{
ll from,to,val,next;
} edge[maxn<<];
struct element
{
ll val,now;
};
bool operator < (element a,element b)
{
if(a.val==b.val)
return a.now<b.now;
return a.val>b.val;
}
void dijikstra(int s,int e)
{
priority_queue<element>q;
memset(dis,0x3f,sizeof(dis));
dis[s]=;
q.push(element{,s});
while(!q.empty())
{
element u=q.top();
q.pop();
if(vis[u.now])
continue;
vis[u.now]=;
for(int i=head[u.now]; i!=-; i=edge[i].next)
{
int to=edge[i].to;
if(dis[u.now]+edge[i].val<dis[to])
{
dis[to]=dis[u.now]+edge[i].val;
q.push(element{dis[to],to});
}
}
}
ll ans=1e18;
for(int i=; i<=k; i++)
{
if(ans>dis[e+i*n])
ans=dis[e+i*n];
}
printf("%lld\n",ans);
}
void init()
{
memset(head,-,sizeof(head));
memset(vis,,sizeof(vis));
cnt=;
}
void edgeadd(ll from,ll to,ll val)
{
edge[cnt].from=from;
edge[cnt].to=to;
edge[cnt].val=val;
edge[cnt].next=head[from];
head[from]=cnt++;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
init();
scanf("%d%d%d",&n,&m,&k);
st=,ed=n;
for(int i=; i<=m; i++)
{
ll x,y,z;
scanf("%lld%lld%lld",&x,&y,&z);
for(int i=; i<=k; i++) //分为k+1层图，
{
edgeadd(x+i*n,y+i*n,z); //每层图之间建边
if(i!=k)
{
edgeadd(x+i*n,y+(i+)*n,);//第层i向i+1层图建边 边权为0;
}
}
}
dijikstra(st,ed);
}
}
BZOJ 2763
dp思想
/**************************************************************
Problem: 2763
User: 1071532391
Language: C++
Result: Accepted
Time:7452 ms
Memory:6972 kb
****************************************************************/ #include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define fillchar(a, x) memset(a, x, sizeof(a))
#define huan printf("\n");
#define debug(a,b) cout<<a<<" "<<b<<" ";
using namespace std;
const int maxn=2e4+,inf=0x3f3f3f3f;
typedef long long ll;
typedef pair<int,int> pii;
struct edge
{
int u,v,w,next;
}e[maxn*];
struct node
{
int x,y;
};
int cnt,dis[maxn][],head[maxn],vis[maxn][];
int n,m,k,s,t;
void init()
{
cnt=;
fillchar(head,-);
fillchar(vis,);
}
void addedge(int u,int v,int w)
{
e[++cnt].next=head[u];
e[cnt].u=u;
e[cnt].v=v;
e[cnt].w=w;
head[u]=cnt;
}
void spfa()
{
fillchar(dis,0x3f);
queue<node> q;
q.push(node{s,k});
dis[s][k]=;
while(!q.empty())
{
int u=q.front().x;
int t=q.front().y;
q.pop();
vis[u][t]=;
for(int i=head[u];i!=-;i=e[i].next)
{
int v=e[i].v,w=e[i].w;
if(dis[v][t]>dis[u][t]+w)
{
dis[v][t]=dis[u][t]+w;
if(!vis[v][t])
{
vis[v][t]=;
q.push(node{v,t});
}
}
if(t>&&dis[v][t-]>dis[u][t])
{
dis[v][t-]=dis[u][t];
if(!vis[v][t-])
{
vis[v][t-]=;
q.push(node{v,t-});
}
}
}
}
int ans=1e9;
for(int i=;i<=k;i++)
{
//cout<<dis[i][0]<<" "<<i<<endl;
ans=min(ans,dis[t][i]);
}
printf("%d\n",ans);
}
int main()
{
init();
scanf("%d%d%d%d%d",&n,&m,&k,&s,&t);
for(int i=;i<m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
addedge(u,v,w);
addedge(v,u,w);
}
spfa();
return ;
}