首页 > 代码库 > poj1125(Stockbroker Grapevine)

poj1125(Stockbroker Grapevine)

2024-07-11 08:37:44   212人阅读

题目大意：

    题目会给你N个经纪人，样例给出的是第几个经纪人与其他经纪人之间的联系和散播需要的时间，问你从哪个经纪人开始传播是散发的谣言最快，以及算出所需要的时间，这里的时间是一条最短路径中所花费时间最少路径。如果存在某个经济人不在最短路中输出”disjoint“。（我没判断就过了，数据shui）

 

解题思路：

    

    最短路径算法dijstra， 循环每一个经纪人，找出花费时间最少路径也就是题目要求的答案。

 

代码：

#include <algorithm>#include <iostream>#include <sstream>#include <cstdlib>#include <cstring>#include <cstdio>#include <string>#include <bitset>#include <vector>#include <queue>#include <stack>#include <cmath>#include <list>//#include <map>#include <set>using namespace std;/***************************************/#define ll long long#define int64 __int64/***************************************/const int INF = 0x7f7f7f7f;const double eps = 1e-8;const double PIE=acos(-1.0);const int d1x[]= {0,-1,0,1};const int d1y[]= {-1,0,1,0};const int d2x[]= {0,-1,0,1};const int d2y[]= {1,0,-1,0};const int fx[]= {-1,-1,-1,0,0,1,1,1};const int fy[]= {-1,0,1,-1,1,-1,0,1};/***************************************/void openfile(){    freopen("data.in","rb",stdin);    freopen("data.out","wb",stdout);}/**********************华丽丽的分割线,以上为模板部分*****************/int map[500][500];int lowcost[500];int vis[500];int n;int ce;int maax;void dijstra(int sta){    int i,j,k=0;    int cnt=0;    int min;    for(i=1; i<=n; i++)    {        lowcost[i]=map[sta][i];        vis[i]=0;    }    vis[sta]=1;    // lowcost[sta]=0;    for(i=1; i<n; i++)    {        min=INF;        for(j=1; j<=n; j++)        {            if (!vis[j]&&lowcost[j]<min)            {                 min=lowcost[j];                 k=j;            }        }        if (k)            cnt++;        if (cnt==n-1)            if (min<maax)            {                maax=min;                ce=sta;            }        vis[k]=1;        for(j=1;j<=n;j++)            if(!vis[j]&&lowcost[j]>lowcost[k]+map[k][j])                lowcost[j]=lowcost[k]+map[k][j];    }}int main(){    while(scanf("%d",&n)&&n)    {        int i,j;        for(i=0; i<500; i++)            for(j=0; j<500; j++)                map[i][j]=INF;        int a;        int u,cost;        for(i=1; i<=n; i++)        {            scanf("%d",&a);            for(j=0; j<a; j++)            {                scanf("%d%d",&u,&cost);                map[i][u]=cost;            }        }        maax=INF;        for(i=1; i<=n; i++)            dijstra(i);        printf("%d %d\n",ce,maax);    }    return 0;}//没有判断disjoint 。可以自己加上。
View Code

 


联系
我们