POJ 1125 暴力+Dijkstra

题目描述：

众所周知，证券经纪业依靠的就是过度的传言。您需要想出股票经纪人中传播假情报的方法，让您的雇主在股票市场的占据优势。为了获得最大的效果，你必须蔓延最快的方式谣言。不幸的是你，股票经纪人信息只信任他们的“可靠来源”，这意味着你在你传播谣言之前必须考虑到他们的接触结构。它需要特定股票经纪人和一定的时间把谣言传递给他的每一位同事。你的任务将是写一个程序，告诉您选择哪一个股票经纪人作为谣言的出发点和所花费多少时间将谣言扩散到整个社会的股票经纪人。这一期限是衡量过去的人收到信息所需的时间。
输入
你的程序包含多组股票经纪人的输入数据。每组以股票经纪人的人数开始。接下来的几行是每个经纪人与其他人接触的一些信息，包括这些人都是谁，以及将讯息传达到他们所需的时间。每个经纪人与其他人接触信息的格式如下：开头的第一个数表示共有n个联系人，接下来就有n对整数。每对整数列出的第一个数字指的是一个联系人（例如，一个'1'是指编号1的人），其次是在传递一个信息给那个人时所采取分钟的时间。没有特殊的标点符号或空格规则。每个人的编号为1至经纪人数目。所花费的传递时间是从1到10分钟（含10分种）。股票经纪的人数范围是从1到100。当输入股票经纪人的人数为0时，程序终止。
输出
在对于每一组数据，你的程序必须输出一行，包括的信息有传输速度最快的人，以及在最后一个人收到消息后，所总共使用的时间（整数分钟计算）。你的程序可能会收到的一些关系会排除一些人，也就是有些人可能无法访问。如果你的程序检测到这样一个破碎的网络，只需输出消息“disjoint”。请注意，所花费的时间是从A传递消息到B，B传递信息到A不一定是花费同样的传递时间，但此类传播也是可能的。

思路：遍历每个节点，求出这个节点到其他节点的最短时间，再从这些最短的时间中选出最大的那个，再从这些最大的时间中选出最小的那个。（呵呵，有点绕口）

看代码：

[cpp]
#include<iostream>
using namespace std;
int n;//节点个数
int map[101][101];//存储边
bool v[101];//标记数组
int dis[101];//起点传播到相应节点的传播时间
int data[101];//节点传播的最长时间
int qian[101];//记录传播中节点的前驱结点

int dij(int form)//求最短时间
{
    int i,j,k=0;
    /* 初始化相应的数组*/
    memset(v,0,101);
    for(i=1;i<=n;i++){data[i]=0;dis[i]=10000000;qian[i]=i;}
    for(i=1;i<=n;i++)
        if(!v[i]&&map[form][i]){dis[i]=map[form][i];qian[i]=form;}
    v[form]=1;
    /*=================*/
    int sum=0;//记录最短时间
    int num=1;//记录遍历的节点个数
    for(i=1;i<n;i++)
    {
        int min=100000;
        for(j=1;j<=n;j++)if(!v[j]&&min>dis[j]){min=dis[j];k=j;}
        if(min==100000)break;//如果min值没改变则图中有独立节点
        v[k]=1;
        if(min>data[qian[k]])
        {
            /*如果min大于前驱节点传播的最大时间，则只需加上min和data[qian[k]]的差，修改前驱节点传播最大时间
              如果min小于前驱结点的传播最大时间，则总传播时间不变*/
            sum+=min-data[qian[k]];
            data[qian[k]]=min;
        }
        num++;
        for(j=1;j<=n;j++)
        {
            if(!v[j]&&map[k][j])
                if(dis[j]>map[k][j]+dis[k]){dis[j]=map[k][j]+dis[k];qian[j]=qian[k];}
        }
    }
    if(num!=n)return 10000000;//图中有独立节点
    else return sum;
}
int main()
{
    while(scanf("%d",&n))
    {
        if(n==0)break;
        memset(map,0,sizeof(map));
        int i,j,k,to,w;
        for(i=1;i<=n;i++)
        {
            cin>>j;
            for(k=1;k<=j;k++)
            {
                cin>>to>>w;
                map[i][to]=w;
            }
        }
        int form=0,min_time=1000000;
        for(i=1;i<=n;i++)
        { www.zzzyk.com
            k=dij(i);
            if(min_time>k){min_time=k;form=i;}
        }
        if(form==0)cout<<"disjoint"<<endl;//图中有鼓励节点
        else cout<<form<<" "<<min_time<<endl;
    }

    return 0;
}

作者：mylovepanning

补充：软件开发 , C++ ,