poj 1125

最短路径问题，我用的是临接表来存储各个边的信息，用优先队列的dijkstra算法
#include <iostream> #include <queue> #include <vector> using namespace std; const int maxn=101; const int INF=2<<20; struct edge {int po,w;edge * next; }; struct node {edge * first; }head[maxn]; typedef pair<int,int>pii; priority_queue<pii,vector<pii>,greater<pii> >q; int n,per,minx; void dijkstra() {int low[maxn],i,j,visit[maxn];minx=INF;for(i=1;i<=n;i++){int max=-1;int tot=0;for(j=1;j<=n;j++){low[j]=j==i?0:INF;visit[j]=0;}q.push(make_pair(low[i],i));while(!q.empty()){pii u=q.top();q.pop();int x=u.second;if(visit[x]) continue;visit[x]=1;tot++;if(low[x]>max)max=low[x];edge * tem=head[x].first;while(tem!=NULL){if(low[tem->po]>(low[x]+tem->w)){low[tem->po]=low[x]+tem->w;q.push(make_pair(low[tem->po],tem->po));}tem=tem->next;}}if(tot==n){if(max<minx){minx=max;per=i;}}} } int main() {while(cin>>n&&n!=0){int i,t,e,w;for(i=1;i<=n;i++) head[i].first=NULL;edge * tem;for(i=1;i<=n;i++){cin>>t;while(t--){cin>>e>>w;tem=new edge;tem->po=e;tem->w=w;tem->next=head[i].first;head[i].first=tem;}}dijkstra();cout<<per<<" "<<minx<<endl;}return 0; }

转载于:https://www.cnblogs.com/lj-vs-lishimin/archive/2012/10/29/2774369.html

总结

以上是生活随笔为你收集整理的poj 1125的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。