poj1062 昂贵的礼物（dijkstra+枚举）-白红宇

poj1062 昂贵的礼物（dijkstra+枚举）

阅读量：5280 次

发布时间：2019-06-14

本文共 1358 字，大约阅读时间需要 4 分钟。

传送门：

题目大意：买东西，每个东西有了替代品，拥有替代品后可以有优惠价格，每个物品的主人有自己的等级，等级超过m的不能直接或者间接交易，问买1号物品的最低价格是多少。

思路：一开始想到dfs，但等级不超过m的比较麻烦，看了别人的做法后发现把这题转化为最短路实在是太巧妙了（我太弱了），一开始的起点是0，表示什么都没有，每个物品的价格就是从0到i的权值，然后优惠价格就是u和i的权值，就这样转化为了最短路，只不过起点是0，终点是1.而等级问题的话，就依次枚举各个节点的等级，假设为最低等级，然后遍历一下，跑一跑迪杰特斯拉，算出最小值。（用这个方法枚举，dfs应该也行）。

具体看代码的注释吧。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  using namespace std;int m,n;const int maxn=110;int dis[maxn],v[maxn],g[maxn][maxn],vis[maxn],vv[maxn];int djks(){ for(int i=1;i<=n;i++){ dis[i]=g[0][i];//表示从0点出发（啥都没有的时候） } dis[0]=0; vis[0]=1; for(int i=1;i<=n;i++){ int p,minn=0x3f3f3f3f; for(int j=1;j<=n;j++){ if(!vis[j]&&dis[j]
                  
                   dis[p]+g[p][j]){ dis[j]=dis[p]+g[p][j]; } } } return dis[1];//（回到1点） }int main(){ scanf("%d%d",&m,&n); memset(g,0x3f3f3f3f,sizeof(g));//图 for(int i=1;i<=n;i++){ int k; scanf("%d%d%d",&g[0][i],&v[i],&k);//u物品到i物品的花费（到达u节点 去i节点的权值） while(k--){ int u,w; scanf("%d%d",&u,&w); g[u][i]=w; } } int minn=0x3f3f3f3f;//答案最小值 for(int i=1;i<=n;i++){//枚举每个节点的等级 将当前节点设为最低等级 int va=v[i]; if(vv[va])continue; vv[va]=1; memset(vis,0,sizeof(vis)); for(int j=1;j<=n;j++){ if(v[j]-va>m)vis[j]=1;//排除掉比自己高m以上的 if(v[j]

转载于:https://www.cnblogs.com/mountaink/p/9536736.html

你可能感兴趣的文章