poj1125 Stockbroker Grapevine 最短路 dijkstral + 优先队列

本文主要是介绍poj1125 Stockbroker Grapevine 最短路 dijkstral + 优先队列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

//    poj1125 Stockbroker Grapevine 最短路 dijkstral + 优先队列
//
//    一个模板吧，留着纪念#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>using namespace std;typedef pair<int,int> P;const int MAX_N = 108;
const int INF = 0x3f3f3f3f;
struct node {int to;int w;int next;node (){}node (int to,int w,int next):to(to),w(w),next(next){}
};node edges[MAX_N * MAX_N];int head[MAX_N];int num;
int n,m;
bool vis[MAX_N];void add_edge(int u,int v,int w){edges[num].to = v;edges[num].w = w;edges[num].next = head[u];head[u] = num++;
}void input(){memset(head,-1,sizeof(head));num = 0;int v,w;for (int i=1;i<=n;i++){scanf("%d",&m);for (int j=1;j<=m;j++){scanf("%d%d",&v,&w);add_edge(i,v,w);}}
}int dijkstra(int s){int d[MAX_N];memset(d,INF,sizeof(d));memset(vis,0,sizeof(vis));d[s] = 0;vis[s] = 1;priority_queue<P,vector<P>,greater<P> > que;que.push(P(0,s));while(!que.empty()){P x = que.top();que.pop();int u = x.second;if (x.first > d[u])    continue;for (int j = head[u] ; j!=-1;j=edges[j].next){int v = edges[j].to;int w = edges[j].w;if (d[v] > d[u] + w){d[v] = d[u] + w;que.push(P(d[v],v));}}}int mx = 0;for (int i=1;i<=n;i++){if (d[i]==INF){return -1;}else if (d[i] > mx){mx = d[i];}}return mx;}void solve(){int k = -1;int mx = INF;for (int i=1;i<=n;i++){int x = dijkstra(i);if (x!=-1){if (mx > x){k = i;mx = x;}}}printf("%d %d\n",k,mx);
}int main(){//freopen("1.txt","r",stdin);while(scanf("%d",&n)!=EOF && n){input();solve();}
}

这篇关于poj1125 Stockbroker Grapevine 最短路 dijkstral + 优先队列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---