首页 > 代码库 > [HNU4]Dwarf Tower

[HNU4]Dwarf Tower

2024-07-14 09:02:34   217人阅读

题意：给你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 }
View Code

 


联系
我们