比赛 20150408 评测结果 AAAAAWETEE
题目名称 牛的路线2 最终得分 50
用户昵称 TA 运行时间 1.646 s
代码语言 C++ 内存使用 103.39 MiB
提交时间 2015-04-08 21:29:00
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#include<iostream>
int ptr[10005],next[10000000],succ[10000000],w[10000000];
int spfatot=1;
int q[10005],dis[10005];
bool flag[10005];
#define Pred(x) x?x-1:0
#define Next(x) x==10003?0:x+1
inline void in(int &x){
	char c=getchar();while(c<'0'||c>'9')c=getchar();
	x=0;
	for(;c>='0'&&c<='9';c=getchar())x=x*10+c-'0';
}
inline void addedge(int from,int to,int cost){
	next[spfatot]=ptr[from],ptr[from]=spfatot,succ[spfatot]=to,w[spfatot++]=cost;
}
int main(){
	freopen("cowrouteb.in","r",stdin);
	freopen("cowrouteb.out","w",stdout);
	int A,B,N;
	in(A),in(B),in(N);
	int son[505],sonsum,cost;
	int i,j,k;
	for(i=0;i<N;++i){
		in(cost),in(sonsum);
		for(j=0;j<sonsum;++j)in(son[j]);
		for(j=0;j<sonsum;++j)
			for(k=j;++k<sonsum;)
				addedge(son[j],son[k],cost);
	}
	int h=0,t=1,x;
	memset(dis,127,sizeof(dis));
	dis[A]=0;
	for(q[0]=A;h!=t;){
		x=q[h],flag[x]=0,h=Next(h);
		for(i=ptr[x];i;i=next[i])
			if(dis[x]+w[i]<dis[succ[i]]){
				dis[succ[i]]=dis[x]+w[i];
				if(!flag[succ[i]]){
					flag[succ[i]]=1;
					if(h==t||dis[succ[i]]<dis[q[h]]){
						h=Pred(h);
						q[h]=succ[i];
					}
					else{
						q[t]=succ[i];
						t=Next(t);
					}
				}
			}
	}
	if(dis[B]>1E7)puts("-1");
	else printf("%d\n",dis[B]);
}