学步园

裸的最短路径问题，这应该是以前的一道月赛题，一开始用floyd写的，这次用spfa+优先队列优化，还有存图的方式和以前不同。。。

题意：求出在哪个点发起谣言，传到每个人的所用的时间最少，以每个点为源点枚举求最短路。。。。

#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
#include<queue>
#define N 105
#define inf 0xfffff
using namespace std;
struct Gnode
{
	Gnode() {}
	Gnode(int num,int time):num(num),time(time) {}
	int num,time;
	bool operator<(const Gnode &now) const
	{return now.time<time;}
};
int dis[N];
void SPFA(vector<vector<Gnode> >&Graph,int start)
{
	priority_queue<int> Q;
	dis[start]=0;
	Q.push(start);
	while(!Q.empty())
	{
		int cur=Q.top();
		 Q.pop();
		 for(int i=0;i<Graph[cur].size();++i)
		 {
			 if(dis[cur]!=inf&&dis[cur]+Graph[cur][i].time<dis[Graph[cur][i].num])
			 { 
				 dis[Graph[cur][i].num]=dis[cur]+Graph[cur][i].time;
				 Q.push(Graph[cur][i].num);
			 }
		 }
	}
}
void init()
{
	for(int i=0;i<N;++i)
		dis[i]=inf;
}
int main()
{
	int n;
	while(cin>>n&&n)
	{
		vector<vector<Gnode> >Graph (n+1);
		for(int i=1;i<=n;++i)
		{
			int num;
			cin>>num;
			for(int j=0;j!=num;++j)
			{
				int a,b;
				cin>>a>>b;
				Graph[i].push_back(Gnode(a,b));
			}
		}
		int minx=inf,p;
		for(int i=1;i<=n;++i)
		{
			init();
			SPFA(Graph,i);
			int maxx=-inf;
			for(int j=1;j<=n;++j)
				maxx=max(dis[j],maxx);
			if(maxx<minx) {p=i;minx=maxx;}
		}
		cout<<p<<" "<<minx<<endl;
	}return 0;
}