题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3268
题目大意：已知每件物品的价格，第i件物品加k金钱可以换取第j件，价格相等的两件物品可以相互交换，求每个物品最小的购买Pi，和有多少个Pi=任意Pj+Pk。
分析：转化成最短路，建立一个新源点s，对每个点加一条边，边权为它的原始价格。对可以价钱交换的点建边，边权为要加的钱，对每对价格相等的点建立边权为0的双向边，做一遍s的最短路即可。第二问简直坑爹，3重循环就办了。
代码：
View Code #include#include #include #include #include using namespace std; #define MaxN 50 struct atp { int y,d,next; }e[MaxN*4];int first[MaxN]; int c[MaxN],Max; int n,m,s,tot=0; int d[MaxN];bool b[MaxN]; queue q; inline void add(int x,int y,int z) { tot++; e[tot].y=y; e[tot].d=z; e[tot].next=first[x]; first[x]=tot; } void init() { int x,y,z; s=0;tot=0; memset(first,0,sizeof(first)); scanf("%d",&n); for (int i=1;i<=n;i++) { scanf("%d%d",&x,&y); add(0,x,y-1); c[x]=y; } for (int i=1;i<=n;i++) { for (int j=1;j<=n;j++) if (i!=j && c[i]==c[j]) add(i,j,0); } scanf("%d",&m); for (int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&z); add(x,y,z); } } void SPFA() { int u; while (!q.empty()) q.pop(); memset(b,false,sizeof(b)); memset(d,100,sizeof(d)); q.push(s);b[s]=true;d[s]=0; while (!q.empty()) { u=q.front();q.pop(); for (int p=first[u];p;p=e[p].next) { if (d[u]+e[p].d