记录编号	465561	评测结果	AAAAAAAAAA
题目名称	找最佳通路	最终得分	100
用户昵称	ユッキー	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2017-10-27 11:30:28	内存使用	0.34 MiB

#include <cstdio>
#include <cstring>
#define inf 999999999
#define maxv 1000
#define maxe 1000
const int lq=maxv+5;
#include <iostream>
using namespace std;
bool vis[maxv];
int dis[maxv];
int a[lq+1];
int u[maxe];
int v[maxe];
int w[maxe];
int first[maxv];
int next[maxv];
int n,m,s,t;
int head,tail;
int main()
{
    register int i,j;
    freopen("city.in","r",stdin);
    freopen("city.out","w",stdout);
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(i=1;i<=n;i++)dis[i]=inf;
    dis[s]=0;
    a[1]=s;
    head=1,tail=2;
    vis[s]=1;
    for(i=1;i<=n;i++)first[i]=-1;
    for(i=1;i<=2*m;i+=2)
    {
        w[i]=1;
        scanf("%d%d",&u[i],&v[i]);
        w[i+1]=w[i];
        u[i+1]=v[i];
        v[i+1]=u[i];
        next[i]=first[u[i]];
        first[u[i]]=i;
        next[i+1]=first[u[i+1]];
        first[u[i+1]]=i+1;
    }
    int tmp;
    while(head<tail)
    {
        tmp=a[head];
        head=(head%lq)+1;
        vis[tmp]=0;
        for(i=first[tmp];i!=-1;i=next[i])
        {
            if(dis[v[i]]>dis[tmp]+w[i])
            {
                dis[v[i]]=dis[tmp]+w[i];
                //pre[v[i]]=tmp;
                if(!vis[v[i]])
                {
                    a[tail]=v[i];
                    tail=(tail%lq)+1;
                    vis[v[i]]=1;
                }
            }
        }
    }
    printf("%d",dis[t]+1);
    return 0;
}