比赛 |
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;
}