POJ 1125-Stockbroker Grapevine
poj
2023-09-11 14:21:02 时间
题意: n个人炒股,每一个人都能够给其它人报信,第 1 行 n,第x行 第一个 是 第 x-1个人能够给几个人报信,后面是能给哪些人报信和报信的时间 ,问从第几个人開始报信所用的时间最少
水题,Floyd 一遍 过;
ME 676KB
TI 16MS
#include <iostream> #include <stdio.h> #include <stdlib.h> #include <math.h> #include <string.h> #include <algorithm> const int INF = 1e7; const int N = 105; using namespace std; int mapp[N][N],n; void init() { for(int i = 1;i<=n;i++) { for(int j = 1;j<=n;j++) { mapp[i][j] = INF; } } } void Floyd() { int k,j,i; for(k = 1;k<=n;k++) { for(i = 1;i<=n;i++) { for(j=1;j<=n;j++) { if(mapp[i][j] > mapp[i][k] + mapp[k][j]) mapp[i][j] = mapp[k][j] + mapp[i][k]; } } } } int main() { int s,wz,ti; while(scanf("%d",&n),n) { init(); for(int i = 1;i<=n;i++) { scanf("%d",&s); for(int j = 1;j<=s;j++) { scanf("%d%d",&wz,&ti); mapp[i][wz] = ti; } } Floyd(); int st = -1,maxx = 0,ti = INF; for(int i = 1;i<=n;i++) { maxx = 0; for(int j = 1;j<=n;j++) { if(i==j) continue; if(mapp[i][j]> maxx) { maxx = mapp[i][j]; } } if(ti>maxx) { ti = maxx; st = i; } } if(st!=-1) printf("%d %d\n",st,ti); else puts("disjoint"); } return 0; }
相关文章
- POJ 2187 Beauty Contest(凸包,旋转卡壳)
- Power Network (poj 1459 网络流)
- POJ 1847 Tram
- POJ 3613 Cow Relays
- poj 3984 bfs
- POJ 3468 A Simple Problem with Integers (线段树)
- POJ 1426 Find The Multiple
- POJ 1961 Period
- POJ 2407 Relatives
- poj 2676 Sudoku
- POJ 2891 Strange Way to Express Integers 中国剩余定理解法
- POJ 1442 Black Box treap求区间第k大
- poj 2503 Babelfish
- POJ 2524--Ubiquitous Religious