一道伪装图论题，比赛连题都没看，哎，真是想想就气。
题目描述
小s想要创造n种魔法宝石。小s可以用ai的魔力值创造一棵第i种魔法宝石，或是使用两个宝石合成另一种宝石（不消耗魔力值）。请你帮小s算出合成某种宝石的所需的最小花费。
输入
第一行为数据组数T（1≤T≤3）。 对于每组数据，首先一行为n,m(1≤n,m≤10^5)。分别表示魔法宝石种类数和合成魔法的数量。 之后一行n个数表示a1到an。(1≤ai≤10^9)。a_i表示合成第i种宝石所需的魔力值。 之后n行，每行三个数a,b,c(1≤a,b,c≤n),表示一个第a种宝石和第b种宝石，可以合成一个第c种宝石。
输出
每组数据输出一行n个数，其中第i个数表示合成第i种宝石的魔力值最小花费。
样例输入
1 3 1 1 1 10 1 2 3 样例输出
1 1 2
可以看出是求每个合成宝石的最小魔力值，不过这里是有些两个宝石可以另一个宝石，故我们只要对这些求一下是直接制造这个宝石魔力值小，还是用两个宝石合成魔力值小。所以，TM可以暴力
第一种暴力写法：
#include<iostream> #include<algorithm> using namespace std; const int MAX = 1e5 + 10; typedef long long ll; ll dis[MAX]; ll a[MAX],b[MAX],c[MAX]; int main(void) { int t; cin >> t; while(t--){ int n,m; cin >> n >> m; for(int i=1;i<=n;i++) dis[i] = 0; for(int i=1;i<=n;i++) cin >> dis[i]; for(int i=1;i<=m;i++){ cin >> a[i] >> b[i] >> c[i]; } for(int i=1;i<=n;i++){ bool checked = false;//判断每次是否被更新 for(int j=1;j<=m;j++){ if(dis[c[j]] > dis[a[j]] + dis[b[j]]){ checked = true; dis[c[j]] = dis[a[j]] + dis[b[j]]; } } if(!checked) break;//如果这一圈没有更新，就直接跳出 } for(int i=1;i<=n-1;++i) cout << dis[i] << " ";//这里要注意输出格式，最后一位数后面不能有空格 cout << dis[n] << endl; } return 0; }第二种SPFA算法 ：
#include<iostream> #include<algorithm> #include<cmath> #include<queue> #include<vector> using namespace std; const int MAX = 1e5 + 10; typedef long long ll; bool used[MAX];//用来标记这个点是否在队列中 struct Edge{ int b; int to; }; ll dis[MAX]; vector<Edge> G[MAX]; int main(void) { int t,n,m; cin >> t; while(t--){ queue<ll> q; cin >> n >> m; for(int i=1;i<=n;i++){ G[i].clear(); dis[i] = 0; used[i] = false; } for(int i=1;i<=n;i++) cin >> dis[i]; ll a,b,c; Edge e; for(int i=1;i<=m;i++){ cin >> a >> b >> c; if(dis[c] > dis[a] + dis[b]){ dis[c] = dis[a] + dis[b]; q.push(c); used[c] = true;//如果这个点发生更新，就把这个点放入队列中。 } e.b = b;e.to = c;//注意这里要用邻接表存两个边 G[a].push_back(e); e.b = a;e.to = c; G[b].push_back(e); } while(!q.empty()){ ll k = q.front(); for(int i=0;i<G[k].size();i++){ e = G[k][i]; if(dis[k] + dis[e.b] < dis[e.to]){ dis[e.to] = dis[k] + dis[e.b]; if(used[e.to] == false){ q.push(e.to); used[e.to] = true; } } } q.pop(); used[k] = false; } for(int i=1;i<=n-1;i++) cout << dis[i] << " ";//输出格式 cout << dis[n] << endl; } return 0; }