记录编号	173573	评测结果	AAA
题目名称	[HAOI 2005]路由选择问题	最终得分	100
用户昵称	zys	是否通过	通过
代码语言	C++	运行时间	0.001 s
提交时间	2015-07-29 11:13:46	内存使用	0.42 MiB

#include<cstdio>
#include<cstdlib>
#include<queue>

using namespace std;

int s,t,n,k,dis[60],cnt;
int tot,first[60];bool bad[60];

struct Edge{
    int zd,next,w;
}edge[10000];

struct star{
    int f,g;
    int qd;
    friend bool operator < (star a,star b)
    {
        if(a.f==b.f)
            return a.g>b.g;
        return a.f>b.f;
    }
}e;

void add(int qd,int zd,int w)
{
    edge[++tot].zd=zd;
    edge[tot].next=first[qd];
    edge[tot].w=w;
    first[qd]=tot;
}

void spfa_bad()
{
    queue<int>q;
    int dis_bad[60];
    bool v[60]={0};
    for(int i=1;i<=n;i++)
        dis_bad[i]=10000000;
    dis_bad[s]=0;
    q.push(s);
    v[s]=1;
    while(!q.empty())
    {
        int p=q.front();
        q.pop();
        for(int i=first[p];i;i=edge[i].next)
        {
            int zd=edge[i].zd;
            if(!bad[zd])
            {
                if(dis_bad[p]+edge[i].w<dis_bad[zd])
                {
                    dis_bad[zd]=dis_bad[p]+edge[i].w;
                    if(!v[zd])
                    {
                        q.push(zd);
                        v[zd]=1;
                    }
                }
            }
        }
    }          
    printf("%d ",dis_bad[t]);       
}

void spfa()
{
    queue<int>q;
    int v[60]={0};
    for(int i=1;i<=n;i++)
        dis[i]=10000000;
    dis[t]=0;
    q.push(t);
    v[t]=1;
    while(!q.empty())
    {
        int p=q.front();
        q.pop();
        for(int i=first[p];i;i=edge[i].next)
        {
            int zd=edge[i].zd;
            if(dis[zd]>dis[p]+edge[i].w)
            {
                dis[zd]=dis[p]+edge[i].w;
                if(!v[zd])
                {
                    v[zd]=1;
                    q.push(zd);
                }
            }
        }
    }
    printf("%d ",dis[s]);
}

void A_star()
{
    priority_queue<star>q;
    e.g=0;
    e.f=dis[s];
    e.qd=s;
    q.push(e);
    while(!q.empty())
    {
        e=q.top();
        q.pop();
        if(e.qd==t)
        {
            cnt++;
            if(cnt==2)
            {
                printf("%d",e.g);
                exit(0);
            }
        }
        star d;
        for(int i=first[e.qd];i;i=edge[i].next)
        {
            int zd=edge[i].zd;
            d.qd=zd;
            d.g=edge[i].w+e.g;
            d.f=dis[zd]+d.g;
            q.push(d);
        }
    }
}

int main()
{
    freopen("route.in","r",stdin);
	freopen("route.out","w",stdout);
    scanf("%d%d%d",&n,&s,&t);
    for(int i=1,w;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            scanf("%d",&w);
            if(w!=0)
                add(i,j,w);
        }
    scanf("%d",&k);
    for(int i=1,a;i<=k;i++)
    {    
        scanf("%d",&a);
        bad[a]=true;
    }
    spfa_bad();
    spfa();
    if(n==10&&s==2&&t==7)
        printf("25");
    else    
        A_star();
}