记录编号	211346	评测结果	AAAAAAAAAA
题目名称	交换	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2015-12-01 10:33:24	内存使用	0.38 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int ans = 1<<25;
const int N = 105;
int level[N];
int num[N];//num[i]:按level升序排序排在第i位的物品的编号
int pos[N];//pos[i]:按level升序排序i号物品的位置，1开始
int d[N][N];//d[i][j]:i号物品用j物品替代的价格。若无法用j替代则为很大的正整数
			//d[i][0]:i物品不替换的价格
			//d[0][i]:i物品替代品数
			//SPFA运行时对d[][]中的数据只读取不修改
int dis[N][N];//SPFA运算时的存储；每运行一遍SPFA初始化一次，按实际编号建图
int q[N];
bool inq[N];
int head = 0,tail = 0;
void add(int n){
	if(!inq[n]){
	q[tail++] = n;
	if(tail == N)tail = 0;
	inq[n] = true;
	}
}
bool cmp(int a,int b){
	return level[a]<level[b];
}
int del(){
	int tmp = q[head++];
	if(head == N)head = 0;
	inq[tmp] = false;
	return tmp;
}
int m,n;
void spfa(int a, int b){
	memset(q,0,sizeof(q));
	memset(inq,0,sizeof(inq));
	memset(dis,127,sizeof(dis));
	head = tail = 0;
	for(int i = a;i<b;++i){
		add(num[i]);
		dis[0][num[i]] = d[num[i]][0];//从void到num[i]号商品
	}
	for(int i = a;i<b;++i){
		dis[num[i]][num[i]] = 0;
		for(int j = a;j<b;++j){
			dis[num[j]][num[i]] = d[num[i]][num[j]];//从num[j]到num[i]商品
		}
	}
	int c;
	while(head!=tail){
		c = del();
		for(int i = a;i<b;++i){
			if(dis[0][c]+dis[c][num[i]]<dis[0][num[i]]){
				dis[0][num[i]] = dis[0][c]+dis[c][num[i]];
				add(num[i]);
			}
		}
	}
	ans = min(ans,dis[0][1]);
}
int main(){
	freopen("swap.in","r",stdin);
	freopen("swap.out","w",stdout);
	memset(d,127,sizeof(d));

	scanf("%d %d",&m,&n);
	int t,v;
	for(int i = 1;i<=n;++i){
		num[i] = i;
		scanf("%d %d %d",d[i],level+i,d[0]+i);
		for(int j = 0;j<d[0][i];++j){
			scanf("%d %d",&t,&v);
			d[i][t]=v;
		}
	}
	//sorting on num[] by level
	sort(num+1,num+n+1,cmp);
	/*for(int i = 1;i<=n;++i){
		pos[num[i]] = i;
	}
	
	for(int i = 1;i<=n;++i){
		copy(num[i],i);
		dis[0][i] = num[i];
	}*/
    int start = 1,end = 1;//SPFA run on [num[start] , num[end])
    while(end<=n&&level[num[end]]-level[num[start]]<=m)end++;//找到第一次spfa的截止点
	while(true){
		spfa(start,end);
	//	printf("start==%d,end==%d,ans==%d\n",start,end,ans);
		if(end==n+1)break;
		while(level[num[end]]-level[num[start]]>m)start++;
		while(end<=n&&level[num[end]]-level[num[start]]<=m)end++;
	}
	printf("%d",ans);
	fclose(stdin);fclose(stdout);
	return 0;
}