首页 > 代码库 > poj1135最短路
poj1135最短路
#include <cstdio>#include <cstring>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>using namespace std;int n,m;const int maxn=505;struct Node{ int x;int val;}node[maxn];struct cmp{ bool operator ()(const Node &a,const Node &b) { return a.val<b.val; }};const int INF=10000000;int dis[maxn];int vis[maxn];int Map[maxn][maxn];void djs(int x){ for(int i=1;i<=n;i++){ dis[i]=INF;vis[i]=0; } dis[x]=0;vis[x]=1; Node k; k.x=x;k.val=0; priority_queue<Node,vector<Node> ,cmp> q; q.push(k); while(!q.empty()){ Node k=q.top();q.pop(); int cur=k.x;vis[x]=1; for(int i=1;i<=n;i++){ if(dis[i]>dis[cur]+Map[cur][i]){ dis[i]=dis[cur]+Map[cur][i]; if(!vis[i]){ Node k; k.x=i;k.val=dis[i]; q.push(k); } } } }}int main(){ int ret=0; while(cin>>n>>m,++ret&&n||m){ for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) Map[i][j]=INF; for(int i=0;i<m;i++){ int a,b,c;cin>>a>>b>>c; if(Map[a][b]>c) Map[a][b]=Map[b][a]=c; } djs(1); double ans=0;int sign=1; for(int i=1;i<=n;i++) if(dis[i]>ans){ ans=dis[i];sign=i; } double ans1=0;int a;int b; for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++)if(Map[i][j]!=INF) { double t=(dis[i]+dis[j]+Map[i][j])/2.0; if(t>ans1) { ans1=t; a=i;b=j; } } } // for(int i=1;i<=n;i++) // cout<<dis[i]<<endl; if(ret!=1) cout<<endl; printf("System #%d\n",ret); if(ans1>ans){ printf("The last domino falls after %.1f seconds, between key dominoes %d and %d.\n",ans1,a,b); } else{ printf("The last domino falls after %.1f seconds, at key domino %d.\n",ans,sign); } } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。