http://poj.org/problem?id=1125

本文主要是介绍http://poj.org/problem?id=1125，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

裸的最短路径问题，这应该是以前的一道月赛题，一开始用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;
}

这篇关于http://poj.org/problem?id=1125的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---