首页 > 代码库 > HNU 12847 Dwarf Tower（最短路+队列优化）

HNU 12847 Dwarf Tower（最短路+队列优化）

2024-07-14 11:48:49   213人阅读

题目链接：http://acm.hnu.cn/online/?action=problem&type=show&id=12847

解题报告：有n样物品，编号从1到n第i样物品可以通过金币vi买到，同时有m种方法，方法的内容是由两种物品可以构造出另一种物品，现在要你求出得到1物品的价值最小是多少？

当成最短路来解，用邻接表存好m种构造方法，然后用队列里面的点去尝试通过构造的方法使得得到i物品所花的价值更小，如果更新成功，再把更新成功的那个点又加入到队列中。

同时要标记一下这个点是不是正在队列中，如果是的话就不要重复加了。直到队列为空结束。

 1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<vector> 6 #include<cmath> 7 #include<deque> 8 using namespace std; 9 const int maxn = 10000+5;10 struct node11 {12     int a,b;13 };14 int w[maxn],visit[maxn];15 vector<node> vt[maxn];16 vector<node>::iterator iter;17 deque<int> de;18 int main()19 {20     int n,m;21     while(scanf("%d%d",&n,&m)!=EOF)22     {23         de.clear();24         for(int i = 1;i <= n;++i)25         vt[i].clear();26         memset(visit,0,sizeof(visit));27         for(int i = 1;i <= n;++i)28         {29             scanf("%d",&w[i]);30             de.push_back(i);31             visit[i] = 1;32         }33         int a,b,c;34         while(m--)35         {36             scanf("%d%d%d",&a,&b,&c);37             node temp = {c,a};38             vt[b].push_back(temp);39             temp.a = b;40             temp.b = a;41             vt[c].push_back(temp);42         }43         while(!de.empty())44         {45             int ss = *de.begin();46             de.pop_front();47             visit[ss] = 0;48             iter = vt[ss].begin();49             for(;iter != vt[ss].end();++iter)50             if(w[ss] + w[iter->a] < w[iter->b])51             {52                 w[iter->b] = w[ss] + w[iter->a];53                 if(visit[iter->b] == 0)54                 {55                     visit[iter->b] = 1;56                     de.push_back(iter->b);57                 }58             }59         }60         printf("%d\n",w[1]);61     }62     return 0;63 }
View Code

 


联系
我们