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