首页 > 代码库 > [HNU4]Dwarf Tower
[HNU4]Dwarf Tower
题意:给你n件物品,每个物品买需要一个价值,m个规则 x,y,z 表示 y z 可以构成 x ,问你最少要多少构成第一个物品,
解题思路:这里用到图论思想,每有一个点更新就把它加入到队列里面等待松弛,但是还是必须要标记
解题代码:
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cstring> 4 #include <algorithm> 5 #include <iostream> 6 #include <cmath> 7 #include <queue> 8 #include <map> 9 #include <stack>10 #include <list>11 #include <vector>12 using namespace std;13 #define LL __int6414 struct node15 {16 int x,y;17 node(LL a,LL b):x(a),y(b){}18 };19 LL a[100010];20 int vis[100010];21 vector <node>v[10010];22 int n,m,i,j,k,x,y;23 queue<int>q;24 int main()25 {26 scanf("%d%d",&n,&m);27 for (i=1;i<=n;i++)28 {29 scanf("%I64d",&a[i]);30 vis[i]=0;31 }32 if (m==0)33 {34 printf("%I64d\n",a[1]);35 return 0;36 }37 for (i=1;i<=m;i++)38 {39 scanf("%d%d%d",&k,&x,&y);40 v[x].push_back(node(y,k));41 v[y].push_back(node(x,k));42 if (!vis[x])43 {44 vis[x]=1;45 q.push(x);46 }47 if (!vis[y])48 {49 vis[y]=1;50 q.push(y);51 }52 }53 while (!q.empty())54 {55 k=q.front();56 vis[k]=0;57 q.pop();58 int l=v[k].size();59 for (i=0;i<l;i++)60 {61 if (a[k]+a[v[k][i].x]<a[v[k][i].y])62 {63 a[v[k][i].y]=a[k]+a[v[k][i].x];64 if (!vis[v[k][i].y])65 {66 q.push(v[k][i].y);67 vis[v[k][i].y]=1;68 }69 }70 }71 }72 printf("%I64d\n",a[1]);73 return 0;74 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。