记录编号	83250	评测结果	AAA
题目名称	[HAOI 2005]路由选择问题	最终得分	100
用户昵称	ranto	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2013-12-01 15:20:30	内存使用	0.32 MiB

#include <fstream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

typedef vector<int>::iterator vit;

ifstream in("route.in");
ofstream out("route.out");

int n;
int s,e;
int **map;
int **map2;
vector<int> bad;

void input();
void ques1();
void ques2();
int djs(int, int, int **);
int djs(int *);//record approachs

int main()
{
	input();
	ques1();
	ques2();
	return 0;
}

void input()
{
	in>> n>> s>> e;
	map=new int *[n+1];
	map2=new int *[n+1];
	map[0]=new int [n+1];
	map2[0]=new int [n+1];
	for(int i=1; i!=n+1; ++i)
	{
		map[i]=new int [n+1];
		map2[i]=new int [n+1];
		for(int j=1; j!=n+1; ++j)
		{
			in>> map[i][j];
			map2[i][j]=map[i][j];
		}
	}
	int b;
	in>>b;
	if(b==0)
	{
		return ;
	}
	for(int i=0; i!=b; ++i)
	{
		int itemp;
		in>>itemp;
		bad.push_back(itemp);
	}
	return ;
}

void ques1()
{
	if(!bad.empty())
	{
		for(vit it(bad.begin()); it!=bad.end(); ++it)
		{
			for(int i=1; i!=n+1; ++i)
			{
				map2[i][*it]=0;
				//map2[*it][i]=0;
			}
		}
	}
	out<< djs(0, 0, map2)<< ' ';
	return ;
}

void ques2()
{
	int *way=new int [n+1];
	memset(way, 0, sizeof(int)*(n+1));
	int min(djs(way));
	out<< min<< ' ';
	int p(e);
	int min2(1<<(8*sizeof(int)-2));
	while(p!=s)
	{
		int itemp(djs(way[p], p, map));
		if(itemp<min2&&itemp>min)
		{
			min2=itemp;
		}
		p=way[p];
	}
	out<< min2<< endl;
	return ;
}

struct node
{
	int now;
	int lenth;
	int next;
	node &operator=(node lh)
	{
		now=lh.now;
		lenth=lh.lenth;
		next=lh.next;
		return *this;
	}
};

bool operator<(node rh, node lh)
{
	return rh.lenth<lh.lenth;
}

bool operator>(node rh, node lh)
{
	return rh.lenth>lh.lenth;
}

int djs(int st, int en, int **m)
{
	priority_queue<node, vector<node>, greater<node> > q;
	int *is=new int [n+1];
	for(int i=1; i!=n+1; ++i)
	{
		is[i]=1;
	}
	node ntemp;
	ntemp.next=s;
	ntemp.lenth=0;
	q.push(ntemp);
	is[s]=0;
	while(!q.empty())
	{
		ntemp=q.top();
		q.pop();
		if(ntemp.next==e)
		{
			return ntemp.lenth;
		}
		int lenth(ntemp.lenth);
		int now(ntemp.next);
		for(int i=1; i!=n+1; ++i)
		{
			if(m[now][i]!=0&& is[i])
			{
				if(now==st&& i==en)
				{
					continue;
				}
				ntemp.next=i;
				ntemp.lenth=lenth+m[now][i];
				q.push(ntemp);
			}
		}
		is[now]=0;
	}
	return 0;
}

int djs(int *ar)
{
	priority_queue<node, vector<node>, greater<node> > q;
	int *is=new int [n+1];
	for(int i=1; i!=n+1; ++i)
	{
		is[i]=1;
	}
	node ntemp;
	ntemp.next=s;
	ntemp.lenth=0;
	q.push(ntemp);
	is[s]=0;
	while(!q.empty())
	{
		ntemp=q.top();
		q.pop();
		if(is[ntemp.next])
		ar[ntemp.next]=ntemp.now;
		if(ntemp.next==e)
		{
			return ntemp.lenth;
		}
		int lenth(ntemp.lenth);
		int now(ntemp.next);
		ntemp.now=now;
		for(int i=1; i!=n+1; ++i)
		{
			if(map[now][i]!=0&&is[i])
			{
				ntemp.next=i;
				ntemp.lenth=lenth+map[now][i];
				q.push(ntemp);
			}
		}
		is[now]=0;
	}
	return 0;
}