软文范例/seo建站营销

这道题比较经典了。建图时用g[0][i] 表示不用替代物品获得编号为i的物品所需的金币，

g[j][i]代表用编号为j的物品替代获得编号为i的物品所需要的金币，然后在M的限制范

围内进行所有可能的交易，最后获得其最小值，一共需要做m次dij。

 

/*Accepted    228K    0MS    C++    1600B    2012-07-26 15:16:49*/
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
using namespace std;
const int MAXN = 1 << 7;
const int inf = 0x3f3f3f3f;
int M, N, g[MAXN][MAXN], lev[MAXN];
typedef pair< int, int> pii;void ReadGragh()
{for( int i = 0; i <= N; i ++)for( int j = 0; j <= N; j ++)g[i][j] = inf;for( int i = 1; i <= N; i ++){int x;scanf( "%d%d%d", &g[0][i], &lev[i], &x);while( x --){int j;scanf( "%d", &j);scanf( "%d", &g[j][i]);}}
}int Dijkstra( int l, int r)
{priority_queue< pii, vector<pii>, greater<pii> > q;int dist[MAXN] = {0};for( int i = 1; i <= N; i ++)dist[i] = inf;q.push( make_pair(0, 0) );while( !q.empty() ){pii u = q.top(); q.pop();int x = u.second;if( u.first > dist[x]) continue;if( x == 1) return dist[1];for( int i = 1; i <= N; i ++){if( l <= lev[i] && lev[i] <= r && dist[i] > dist[x] + g[x][i]){dist[i] = dist[x] + g[x][i];q.push( make_pair( dist[i], i));}}}return 0;
}int main()
{int ans;while( scanf( "%d%d", &M, &N) == 2){ans = inf;ReadGragh();for( int i = lev[1] - M; i <= lev[1]; i ++) //在M的范围内交易
        {ans = min( ans, Dijkstra( i, i + M) );}printf( "%d\n", ans);}return 0;
}