记录编号	161881	评测结果	AAAAAAAAAA
题目名称	[NOI 1997]最优乘车	最终得分	100
用户昵称	raywzy	是否通过	通过
代码语言	C++	运行时间	0.160 s
提交时间	2015-05-10 21:39:00	内存使用	15.69 MiB

#include<cstdio>
#include<cstring>
#include<cmath>
#include<deque>
#include<iostream>
#include<vector>
#define INF 99999999
using namespace std;
class Node
{
public:
    int to,v;
};
int T,N,M,now;
vector<int> A[2005];
int adj[2005][2005];
bool tag[2005];
int dist[2005];
bool flag[2005];
void SPFA()
{
    dist[0]=0;int temp,i;
    deque<int> Q;flag[0]=1;
    Q.push_back(0);
    while(!Q.empty())
    {
        temp=Q.at(0);
        Q.pop_front();
        for(i=0;i<=now;i++)
        {
            if(adj[temp][i]!=-1&&dist[i]>dist[temp]+adj[temp][i])
            {
                dist[i]=dist[temp]+adj[temp][i];
                if(flag[i]==0)
                {
                    flag[i]=1;
                    Q.push_back(i);
                }
            }
        }
        flag[temp]=0;
    }
}
char a[2005];
int F[2005];

int fun()
{
    int j = 0;
    int cc = 0;
    int len = strlen(a);

    for(int i = 0;i <= len;i++)
    {
        if(isdigit(a[i]))
        {
            j *= 10;
            j += a[i]-'0';
        }
        else
        {
            F[cc++] = j;
            j= 0;
        }
    }
    return cc;

}


int main()
{
	freopen("bustravel.in","r",stdin);
	freopen("bustravel.out","w",stdout);
    int i,j,k;Node temp;
        memset(dist,63,sizeof(dist));
        memset(flag,0,sizeof(flag));
        memset(tag,0,sizeof(tag));
        memset(adj,-1,sizeof(adj));
        scanf("%d%d",&N,&M);
        now=M;
        getchar();

        for(i=1;i<=N;i++)
        {
            gets(a);
            int cc = fun();
            for(j=0;j<cc;j++)
            {
                if(tag[F[j]]==1)
                {
                   now++;
                   A[F[j]].push_back(now);
                   F[j]=now;
                }
                else
                    tag[F[j]]=1;
            }
            for(j=0;j<cc-1;j++)
                adj[F[j]][F[j+1]]=0;
        }
        for(i=1;i<=M;i++)
            A[i].push_back(i);
        for(i=1;i<=M;i++)
            for(j=0;j<A[i].size();j++)
                for(k=0;k<A[i].size();k++)
                {
                    if(adj[A[i][j]][A[i][k]]!=0)
                        adj[A[i][j]][A[i][k]]=1;
                }
        for(i=0;i<A[1].size();i++)
            adj[0][A[1][i]]=0;
        now++;
        for(i=0;i<A[M].size();i++)
            adj[A[M][i]][now]=0;
        SPFA();
        if(dist[now]>INF)
            printf("NO\n");
        else
            printf("%d\n",dist[now]);
        for(i=0;i<=now;i++)
            A[i].clear();
    return 0;
}