题目连接：

Description

Little Vasya is playing a new game named “Dwarf Tower”. In this game there are n different items,

which you can put on your dwarf character. Items are numbered from 1 to n. Vasya wants to get the

item with number 1.

There are two ways to obtain an item:

• You can buy an item. The i-th item costs ci money.

• You can craft an item. This game supports only m types of crafting. To craft an item, you give

two particular different items and get another one as a result.

Help Vasya to spend the least amount of money to get the item number 1.

Input

The first line of input contains two integers n and m (1 ≤ n ≤ 10 000; 0 ≤ m ≤ 100 000) — the number

of different items and the number of crafting types.

The second line contains n integers ci — values of the items (0 ≤ ci ≤ 109

The following m lines describe crafting types, each line contains three distinct integers ai, xi, yi — ai is the item that can be crafted from items xi and yi (1 ≤ ai , xi , yi ≤ n; ai ̸= xi ; xi ̸= yi ; yi ̸= ai).

Output

The output should contain a single integer — the least amount of money to spend.

Sample Input

5 3

5 0 1 2 5

5 2 3

4 2 3

1 4 5

Sample Output

题意：

　　对与一个物品，你可以选择购买获得，但是要花费ci ，或者是通过 xi yi 合成。

　　要你用最小的花费得到物品1.

题解：

　　我们对于每一个物品都应该花最小的花费的到。 a可以通过x， y合成。那么从x去到a的费用就是 c[y] 。（因为你已经跑到了x点，表示你已经有了x了）。

　　在建一个大原点 0， 0到每个点的费用为c[i] 。然后用0这里跑一次Dij 。这样你就可以得到了获得物品i 的最小花费。

　　在跑一下m次合成，找到最小的花费。

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
               10 #include 
               
                 11 #include 
                
                  12 using namespace std; 13 typedef long long LL; 14 typedef unsigned long long uLL; 15 #define ms(a, b) memset(a, b, sizeof(a)) 16 #define rep(a, b) for(int a = 0;a
                 
                   r.c; 33 } 34 }; 35 struct Edge { 36 int v, cost; 37 Edge(int _v=0, int _cost =0):v(_v), cost(_cost) {} 38 }; 39 vector 
                  
                    E[10*maxn]; 40 bool vis[maxn]; 41 LL dist[maxn]; 42 void Dij(int n, int start) { 43 memset(vis,false,sizeof(vis)); 44 for(int i=1; i<=n; i++)dist[i]=INF; 45 priority_queue
                   
                    que; 46 while(!que.empty())que.pop(); 47 dist[start]=0; 48 que.push(qnode(start,0)); 49 qnode tmp; 50 while(!que.empty()) { 51 tmp=que.top(); 52 que.pop(); 53 int u=tmp.v; 54 if(vis[u])continue; 55 vis[u]=true; 56 for(int i=0; i
                    
                     dist[u]+cost) { 60 dist[v]=dist[u]+cost; 61 que.push(qnode(v,dist[v])); 62 } 63 } 64 } 65 } 66 void addedge(int u, int v, int w) { 67 E[u].pb(Edge(v, w)); 68 } 69 vector
                     
                      
                        > One; 70 void solve() { 71 int n, m, x, a, b; 72 scanf("%d%d", &n, &m); 73 for(int i = 1; i<=n; i++) { 74 scanf("%d", &c[i]); 75 addedge(0, i, c[i]);//0指向物品i，表示直接购买的花费 76 } 77 for(int i = 1; i<=m; i++) { 78 scanf("%d%d%d", &x, &a, &b); 79 addedge(a, x, c[b]);//a指向物品x，表示需要在花费c[b]的花费就可以合成x 80 addedge(b, x, c[a]); 81 if(x==1){ //记录一下物品1的合成 82 One.pb(mp(a, b)); 83 } 84 } 85 Dij(n, 0); 86 LL ans = dist[1];//得到1的花费 87 for(int i = 0;i

View Code

转载于:https://www.cnblogs.com/denghaiquan/p/7271307.html

你可能感兴趣的文章