Problem D. Dwarf Tower（最短路）

Problem D. Dwarf Tower Input file: dwarf.in Output file: dwarf.out Time limit: 2 seconds Memory limit: 256 megabytes 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 ≤ 10 9 ). 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. Examples dwarf.in dwarf.out 5 3 5 0 1 2 5 5 2 3 4 2 3 1 4 5 2 3 1 2 2 1 1 2 3

2

思路是求最短路，具体解释见代码：

#include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <vector> using namespace std; const int maxn = 1e4+5; const int INF = 1e9; typedef long long ll; ll c[maxn]; int n; vector<pair<ll,ll> > G[maxn];//G[i]代表从i点开始终点是pair.first,pair.second是可以用来换终点物品的另一个物品的价值 ll dis[maxn];//每个物品最少花费，或可以想成一个图外点0到每个物品的最短路 pair<ll,ll> edge[maxn*10];//记录可以1直接交换的两个物品 void dijkstra(){ priority_queue<pair<ll,ll> > q; for(int i = 1; i <= n; i++){ dis[i] = INF;//初始都设为无穷 } q.push(make_pair(0,0));//此时优先队列中的pair两个元素含义有变化first代表到点pos花费的dis，second代表这个点pos //之所以和vector中的储存顺序相反是因为优先队列按照pair的first元素排序 dis[0] = 0; while(!q.empty()){ pair<ll,ll> s = q.top(); q.pop(); ll cost = -s.first;//这里花费我们取了相反数，因为我们入队时放进去的花费是取了相反数，因为优先队列默认大顶堆 //而我们每次需要花费最小的那个，所以去相反数后我们需要的那个最小的花费变成了最大的就顺利先出来了 ll pos = s.second; if(cost > dis[pos]) continue;//如果这个点的花费比并不是最小的跳过 for(int i = 0; i < G[pos].size(); i++){ pair<ll,ll> tmp = G[pos][i]; ll to = tmp.first; ll another_cost = tmp.second; if(dis[to] > cost + another_cost){//pos的花费是cost，从pos点指向to通过vector的记录的花费是与pos配对的物品花费巧妙的得到了两个物品的花费，就可以求和比较终点花费大小了 dis[to] = cost + another_cost; q.push(make_pair(-dis[to],to)); } } } } int main(){ freopen("dwarf.in", "r", stdin); freopen("dwarf.out", "w", stdout);//这两句必须要写否则答案错误 int m; while(scanf("%d%d",&n,&m) != EOF){ for(int i = 0; i <= n; i++) G[i].clear(); for(int i = 1; i<= n; i++){ scanf("%lld",&c[i]); G[0].push_back(make_pair(i,c[i]));//创建一个图外点0，从0开始算到每个点的最短路，初始距离就是每个物品原本的价值 } int cnt = 0; while(m--){ int to,x,y;//x，y换to x->to,y->to; scanf("%d%d%d",&to,&x,&y); G[x].push_back(make_pair(to,c[y])); G[y].push_back(make_pair(to,c[x]));//交叉储存，这样就把两个点联系起来了 if(to == 1){ edge[cnt++] = make_pair(x,y);//储存下直接可以和1交换的每对物品 //更新完最短路后只需要枚举一遍取最小的即可 } } dijkstra();//更新最短路（最小花费） ll ans = dis[1]; for(int i = 0; i < cnt; i++){//枚举求得最小花费 int x = edge[i].first; int y = edge[i].second; ans = min(ans,(dis[x]+dis[y])); } printf("%lld\n",ans); } return 0; }