首页 > 代码库 > 【UVA】821-Page Hopping(Floyd)
【UVA】821-Page Hopping(Floyd)
模板题,求一个点到任何一点的距离,用Floyd就行了,结点不一定是从1 ~ n 的,所以需要记录结点的id
14063895 | 821 | Page Hopping | Accepted | C++ | 0.119 | 2014-08-19 10:00:27 |
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<vector> #include<stack> #include<queue> #include<map> #include<set> #include<list> #include<cmath> #include<string> #include<sstream> #include<ctime> using namespace std; #define _PI acos(-1.0) #define INF (1 << 10) #define esp 1e-9 typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> pill; /*=========================================== ===========================================*/ #define MAXD 100 + 10 int G[MAXD][MAXD]; int main(){ int a , b; int Case = 1; while(scanf("%d%d",&a,&b)){ if(!a && !b) break; for(int i = 1 ; i <= 100 ; i++) for(int j = 1; j <= 100 ; j++) if(i == j) G[i][j] = 0; else G[i][j] = INF; map<int,int>vis; vector<int>node; G[a][b] = 1; while(scanf("%d%d",&a,&b)){ if(!a && !b) break; G[a][b] = 1; if(!vis.count(a)){ node.push_back(a); vis[a] = 1; } if(!vis.count(b)){ node.push_back(b); vis[b] = 1; } } for(int k = 0 ; k < node.size() ; k++) for(int i = 0 ; i < node.size() ; i++) for(int j = 0 ; j < node.size() ; j++) if(G[node[i]][node[k]] < INF && G[node[k]][node[j]] < INF) G[node[i]][node[j]] = min(G[node[i]][node[j]],G[node[i]][node[k]] + G[node[k]][node[j]]); int sum = 0; for(int i = 0 ; i < node.size() ; i++) for(int j = 0 ; j < node.size() ; j++){ sum += G[node[i]][node[j]]; } double ans = 1.0 * sum / ((node.size() -1)* node.size()); printf("Case %d: average length between pages = %.3f clicks\n",Case++,ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。