题目比较好懂的,给个无向图,每条边有个距离,而且走过每条边会获得10个东西,从s出发到t,求要得到k个东西的最短路是多少
如果没这个要拿k个东西的条件,那就是一个简单的最短路,然后这题数据不是很大,可以用bfs来求最短路,当s==t && tk>=k就结束,而与普通的bfs不同的就是我们还要加上一个松弛操作
其中dp[i][j]表示节点i获得j个东西的最短路
if(dp[v][tk+1]>dp[tp][tk]+edge[i].w){
dp[v][tk+1]=dp[tp][tk]+edge[i].w;
q.push(node{
v,tk+1,dp[v][tk+1]});
}
代码:
#include <bits/stdc++.h>
using namespace std;
const int M=200050;
const int N=5050;
const int INF=0x3f3f3f3f;
struct Edge{
int v,w,next;
}edge[M];
int cnt,head[N];
void init(){
cnt=0;
memset(head,-1,sizeof(head));
}
void addEdge(int u,int v,int w){
edge[cnt]=Edge{
v,w,head[u]};
head[u]=cnt++;
edge[cnt]=Edge{
u,w,head[v]};
head[v]=cnt++;
}
int n,m;
int u,v,w;
int s,t,k;
struct node{
int pp,kk,cc;
friend bool operator <(node a,node b){
return a.cc>b.cc;
}
}tmp;
//dp[i][j]表示i点得到j*10个的最短路
int dp[N][60];
int bfs(){
memset(dp,INF,sizeof(dp));
priority_queue<node> q;
q.push(node{
s,0,0});
dp[s][0]=0;
while(!q.empty()){
tmp=q.top();
q.pop();
int tp=tmp.pp;
int tk=tmp.kk;
int tc=tmp.cc;
if(tp==t && tk>=k){
return tc;
}
for(int i=head[tp];i!=-1;i=edge[i].next){
int v=edge[i].v;
if(dp[v][tk+1]>dp[tp][tk]+edge[i].w){
dp[v][tk+1]=dp[tp][tk]+edge[i].w;
q.push(node{
v,tk+1,dp[v][tk+1]});
}
}
}
return -1;
}
int main(void){
while(~scanf("%d%d",&n,&m)){
init();
while(m--){
scanf("%d%d%d",&u,&v,&w);
addEdge(u,v,w);
}
scanf("%d%d%d",&s,&t,&k);
if(k%10){
k=k/10+1;
}else{
k=k/10;
}
int ans=bfs();
printf("%d\n",ans);
}
return 0;
}