首页 > 代码库 > More lumber is required

More lumber is required

2024-07-12 09:06:27   219人阅读

hdu4396:http://acm.hdu.edu.cn/showproblem.php?pid=4396

题意：一个无向带权图，然后给出起点s，终点e，让你求s到e的最短路径，但是这里的路径有要求的。每经过一条边会得到10单位的财富，这条路径必须得到的财富至少k值。

题解：一开始以为是DP，看了别人的代码，才知道了这就是传说中的二维最短路径。然后学习了一下，其实，就是图上的DP。dist[i][j]表示到达i点得到j个财富的最短路径。然后，利用spfa跑最短路，在这个过程中不断更新dist数组，最终的dist[e][k]就是所求的答案。

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 #define  inf  100000000 7 using namespace std; 8 int n,m; 9 int s,e,k;10 struct  Edge{11    int v;12    int val;13    int next;14 }edge[200002];15 int dist[5003][505],vis[5003][505];16 struct Node{17   int pos,num;18 };19 int head[5005];20 int cnt;21 void init(){22   cnt=0;23   memset(head,-1,sizeof(head));24 }25 void addedge(int u,int v,int val){26     edge[cnt].v=v;27     edge[cnt].val=val;28     edge[cnt].next=head[u];29     head[u]=cnt++;30 }31 int SPFA(int s,int e,int k){32     for(int i=1;i<=n;i++)33         for(int j=0;j<=k;j++)34             dist[i][j]=inf;//初始化35       memset(vis,0,sizeof(vis));36       Node tmp;37       tmp.pos=s;38       tmp.num=0;39       dist[s][0]=0;40       vis[s][0]=1;41      queue<Node>Q;42      Q.push(tmp);43      while(!Q.empty()){44         Node t=Q.front();45         Q.pop();46         vis[t.pos][t.num]=0;//可能会多次加到队列47         for(int i=head[t.pos];i!=-1;i=edge[i].next){48             Node tp;49             tp.pos=edge[i].v;50             tp.num=t.num+10;51             if(tp.num>k)52             tp.num=k;//题目是至少得到k，所以在以相同路径长度当到达e时候能得到更多的财富是符合要求的53             if(dist[tp.pos][tp.num]>dist[t.pos][t.num]+edge[i].val){//更新dist数组54                 dist[tp.pos][tp.num]=dist[t.pos][t.num]+edge[i].val;55                 if(vis[tp.pos][tp.num]==0){//如果不在队列，则把这个加入队列56                     vis[tp.pos][tp.num]=1;57                     Q.push(tp);58                 }59             }60         }61      }62       if(dist[e][k]==inf)return -1;63       else64         return dist[e][k];65 }66 int main(){67     int a,b,c;68    while(~scanf("%d%d",&n,&m)){69       init();70       for(int i=1;i<=m;i++){//建图71          scanf("%d%d%d",&a,&b,&c);72          addedge(a,b,c);73          addedge(b,a,c);74       }75         scanf("%d%d%d",&s,&e,&k);76         int ans=SPFA(s,e,k);77         printf("%d\n",ans);78    }79 80 }
View Code


联系
我们