题目链接：
HDU 3268 Columbus’s bargain
题意：
已知每件物品的价格，有四种选择：
①：直接买
②：用一个galss bead + price - 1 个金币
③：等价物品互换
④：第i件物品加k金钱可以换取第j件
求购买每个物品最小金币，和有多少个Pi=任意Pj+Pk。
分析：
最短路啊，很坑啊~
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cassert>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
typedef long long ll;
const int MAX_N = 30;int T, n, m;
int vis[MAX_N], ans[MAX_N], w[MAX_N][MAX_N];inline void work()
{for(int k = 1; k <= n; k++){for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){w[i][j] = min(w[i][k] + w[k][j], w[i][j]);}}}
}int main()
{IOS;cin >> T;while(T-- > 0){cin >> n;for(int i = 1; i <= n; i++){int t, tt;cin >> t >> tt;ans[t] = tt - 1;}for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){if(ans[j] == ans[i]) w[i][j] = 0; //必须是严格ans[j] == ans[i]，才可以//如果定义当ans[j] > ans[i]时 w[i][j] = ans[j] - ans[i];就会WAelse w[i][j] = 1000;}}cin >> m;for(int i = 0; i < m; i++){int u, v, t;cin >> u >> v >> t;w[u][v] = min(w[u][v], t);}work(); //用Floyd对边权进行优化for(int k = 1; k <= n; k++){ //再跑一次Floyd对最终答案进行优化for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){ans[i] = min(ans[j] + w[j][i], ans[i]);}}}int num = 0;for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){if(i == j) continue; int ok = 0;for(int k = 1 ; k <= n; k++){if(k == i || k == j) continue;if(ans[i] == ans[j] + ans[k]) {ok = 1; //ok标记防止重复num ++;break;}}if(ok) break;}}for(int i = 1; i <= n; i++){cout << i << " " << ans[i] << endl;}cout << num << endl;}return 0;
}