比赛 20150408 评测结果 AAAAWWTTTT
题目名称 牛的路线2 最终得分 40
用户昵称 Asm.Def 运行时间 4.008 s
代码语言 C++ 内存使用 39.67 MiB
提交时间 2015-04-08 20:47:18
显示代码纯文本
/***********************************************************************/
/**********************By Asm.Def-Wu Jiaxin*****************************/
/***********************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cctype>
#include <algorithm>
using namespace std;
#define SetFile(x) ( freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout) );
#define getc() getchar() 
template<class T>inline void getd(T &x){
	char ch = getc();bool neg = false;
	while(!isdigit(ch) && ch != '-')ch = getc();
	if(ch == '-')ch = getc(), neg = true;
	x = ch - '0';
	while(isdigit(ch = getc()))x = x * 10 - '0' + ch;
	if(neg)x = -x;
}
/***********************************************************************/
const int maxn = 10003, inf = 0x3f3f3f3f;
int Route[501][503], R_cnt[maxn], A, B, N, dis[maxn], Vcnt;
struct ESet{int *begin, w;}E[maxn][501];
bool exi[maxn];
inline void init(){
	getd(A), getd(B), getd(N);
	int i, j, t, w, cnt;
	for(i = 0;i < N;++i){
		getd(w), getd(cnt);
		for(j = 0;j < cnt;++j){
			getd(t);Route[i][j] = t;
			if(!exi[t])exi[t] = true, ++Vcnt;
			E[t][R_cnt[t]].begin = Route[i] + j;
			E[t][R_cnt[t]++].w = w;
		}
		Route[i][cnt] = -1;
	}
	memset(dis, 0x3f, sizeof(dis));dis[A] = 0;
}
//Heap
#define L(x) (x << 1)
#define R(x) ((x << 1) + 1)
#define P(x) (x >> 1)
int Heap[maxn], ptr[maxn], size;
inline bool validup(int x){return x == 1 || dis[Heap[P(x)]] <= dis[Heap[x]];}
inline bool validdown(int x){
	if(L(x) > size)return true;if(dis[Heap[L(x)]] > dis[Heap[x]])return false;
	return R(x) > size || dis[Heap[R(x)]] >= dis[Heap[x]];
}
inline void MtDown(int x){
	int tmp, repl;
	while(!validdown(x)){
		tmp = dis[Heap[x]];
		if(L(x) < tmp)repl = L(x), tmp = dis[Heap[L(x)]];
		if(R(x) <= size && R(x) < tmp)repl = R(x);
		swap(Heap[x], Heap[repl]);
		swap(ptr[Heap[x]], ptr[Heap[repl]]);
		x = repl;
	}
}
inline void MtUp(int x){
	while(!validup(x)){
		swap(Heap[x], Heap[P(x)]);
		swap(ptr[Heap[x]], ptr[Heap[P(x)]]);
		x = P(x);
	}
}
bool inheap[maxn], known[maxn];
inline int PopMin(){int ans = Heap[1];swap(Heap[1], Heap[size--]);inheap[ans] = false;ptr[Heap[1]] = 1;MtDown(1);return ans;}
inline void Insert(int x){inheap[x] = true;Heap[++size] = x;ptr[Heap[size]] = size;MtUp(size);}
//Heap

#define LoopAdj(u, it, i) for(i = 0;i < R_cnt[u];++i)for(it = E[u][i].begin + 1;~(*it);++it)
inline void work(){
	Insert(A);
	int u, i, *it;
	LoopAdj(A, it, i)if(E[A][i].w < dis[*it]){

		//printf("%d->%d, val=%d\n", A, *it, E[A][i].w);

		dis[*it] = E[A][i].w;
		if(!inheap[*it])Insert(*it);
		else MtUp(ptr[*it]);
	}
	while(!known[B] && size){
		u = PopMin();known[u] = true;
		/*for(i = 1;i <= size;++i){

			printf("Heap[%d] = %d, dis = %d\n", i, Heap[i], dis[Heap[i]]);

		}*/
		LoopAdj(u, it, i)if(!known[*it] && dis[*it] > dis[u] + E[u][i].w){

			//printf("%d->%d, val=%d\n", u, *it, E[u][i].w);

			dis[*it] = dis[u] + E[u][i].w;
			if(!inheap[*it])Insert(*it);
			else MtUp(ptr[*it]);
		}
	}
	printf("%d\n", dis[B] == inf ? -1 : dis[B]);
}

int main(){

#ifdef DEBUG
	freopen("test.txt", "r", stdin);
#elif !defined ONLINE_JUDGE
	SetFile(cowrouteb);
#endif
	init();
	work();
#ifdef DEBUG
	printf("\n%lf sec \n", (double)clock() / CLOCKS_PER_SEC);
#endif
	return 0;
}