题意：给你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 __int64 14 struct node 15 { 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 ",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 ",a[1]); 73 return 0; 74 }