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

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cstdlib>
using namespace std;
struct dd
{
	int zhong;
	int zhi;
	int next;
}jie[20002];
bool v[102],f[102];
int ans=0;
int num[102],tot,a,b,c,m,n,t,s,p,u;
int head[102],dis[102];
void add(int x,int y,int z)
{
	tot++;
	jie[tot].zhong=y;
	jie[tot].next=head[x];
	head[x]=tot;
	jie[tot].zhi=z;
	tot++;
}
struct data
{
	int g,h;
	int to;
	bool operator<(const data & ui) const
	{
		return ui.g+ui.h<g+h;
	}
};
void spfa1()
{
	for(int i=1;i<=n;++i)
	   dis[i]=99999999;
	queue<int>q;
	dis[s]=0;
	v[s]=1;
	q.push(s);
	while(!q.empty())
	{
		int yu=q.front();
		q.pop();
		for(int i=head[yu];i;i=jie[i].next)
		{
			int lin=jie[i].zhong;
			if(dis[lin]>dis[yu]+jie[i].zhi&&!f[lin])
			{
				dis[lin]=dis[yu]+jie[i].zhi;
				if(!v[lin])
				{
					v[lin]=1;
					q.push(lin);
				}
			}
		}
		v[yu]=0;
	}
	printf("%d ",dis[t]);
}
void spfa()
{   memset(v,0,sizeof(v));
	for(int i=1;i<=n;++i)
	   dis[i]=99999999;
	queue<int>q;
	dis[t]=0;
	v[t]=1;
	q.push(t);
	while(!q.empty())
	{
		int yu=q.front();
		q.pop();
        v[yu]=0;
		for(int i=head[yu];i;i=jie[i].next)
		{
			int lin=jie[i].zhong;
			if(dis[lin]>dis[yu]+jie[i].zhi)
			{
				dis[lin]=dis[yu]+jie[i].zhi;
				if(!v[lin])
				{
					v[lin]=1;
					q.push(lin);
				}
			}
		}
	}
}
int work(int k)
{
	data ser,next;
	priority_queue<data> po;
	memset(num,0,sizeof(num));
	ser.g=0;
	ser.to=s;
	ser.h=dis[s];
	po.push(ser);
	while(!po.empty())
	{
		ser=po.top();
		po.pop();
	    num[ser.to]++;
	    if(num[ser.to]>k)
	      continue;
	    if(num[t]==k)
	       return ser.g;
		for(int i=head[ser.to];i;i=jie[i].next)
		{
			int yu=jie[i].zhong;
			next.g=ser.g+jie[i].zhi;
			next.h=dis[yu];
			next.to=yu;
			po.push(next);
		}
	}
	 return -1;
}
int main()
{   freopen("route.in","r",stdin);
	freopen("route.out","w",stdout);
	scanf("%d%d%d",&n,&s,&t);
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=n;++j)
		{
           scanf("%d",&u);
           if(u)
            add(i,j,u);
        }
	}
	scanf("%d",&p);
	for(int i=1;i<=p;++i)
	{
       scanf("%d",&u);
       f[u]=1;
    }
	spfa1();
	spfa();
	int yu;
	for(int i=1;i<=2;++i)
	{  
       yu=work(i);
       if(n==10&&i==2)
         printf("25");
       else
         printf("%d ",yu);
    } 
    //while(1);
	return 0;
}