比赛 20161215 评测结果 AAAAAWWWWW
题目名称 牛的路线2 最终得分 50
用户昵称 Arrow 运行时间 0.033 s
代码语言 C++ 内存使用 0.47 MiB
提交时间 2016-12-16 21:54:16
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<vector>
#define INF 0x7fffffff
using namespace std;
namespace IO{
	char buf[1<<15],*fs,*ft;
	inline char gc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
	inline int read(){
		int x=0,rev=0,ch=gc();
		while(ch<'0'||ch>'9'){if(ch=='-')rev=1;ch=gc();}
		while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=gc();}
		return rev?-x:x;
	}
}using namespace IO;
/*AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA*/
int w[510]={0};
bool end[510]={0},able[510]={0};
vector <int> city[10010];
vector <int> chazhao;
vector <int> path[510];
int main()
{
	freopen("cowrouteb.in","r",stdin);
	freopen("cowrouteb.out","w",stdout);
	int a,b,n,flaga=0,flagb=0,ans=INF,now=0,flag1=0,flag2=0,flag=0;
	a=read();b=read();n=read();
	for(int i=1;i<=n;i++)
	{
		int x=read();
		w[i]=x;
		int y=read();
		for(int j=1;j<=y;j++)
		{
			int point=read();
			if(flagb==0)
			city[point].push_back(i);
			if(flaga==1)
				path[i].push_back(point);
			if(point==a&&j!=y){
				chazhao.push_back(i);
				flaga=1;
				flag1=1;
			}
			if(flaga==1&&point==b)
			{
				now=w[i];
				if(now<ans)
				ans=now;
				able[i]=1;
			}
			if(point==b)
			{
				flagb=1;
				end[i]=1;
				flag2=1;
			}
			
		}
		flaga=0;flagb=0;
	}
	if(!(flag1==1&&flag2==1)){
		printf("-1\n");
		return 0;
	}
	for(int i=0;i<chazhao.size();i++)
	{
		now=0;
		now+=w[chazhao[i]];
		able[chazhao[i]]=1;
		for(int j=0;j<path[chazhao[i]].size();j++)
		{
			for(int k=0;k<city[path[chazhao[i]][j]].size();k++)
			{
				if(end[city[path[chazhao[i]][j]][k]]==1&&able[city[path[chazhao[i]][j]][k]]==0)
				{
					now+=w[city[path[chazhao[i]][j]][k]];
					flag=1;
				    if(now<ans)
					   ans=now;
				}
			}
		}
		able[chazhao[i]]=0;
	}
	if(flag==0)
	{
		printf("-1\n");
		return 0;
	}
	printf("%d\n",ans);
return 0;
}