Sicily 1308 Dependencies among J (SOJ 1308)「BFS 广度优先搜索」

0.00 avg. rating (0% score) - 0 votes
转载请注明: 吹水小镇 | reetsee.com
原文链接地址: http://blog.reetsee.com/archives/124

原题地址:点击打开链接

一开始以为是拓扑排序,因为看上去比较像,等写了一半后发现实际这题的做法和广搜是一样的。

——————正文——————

根据输入可以建立一个有向图,从目标点m开始,向前寻找其紧前节点,然后将所有这些紧前节点(包括紧前节点的紧前节点)的时间值加起来就可以了。

寻找所有这样的节点的方法就是用广搜的方法,使用队列即可。

比较简单的一个题目,就不画图了。

这题如果使用cin可能会TLE,另外是对于一整行的输入,我使用的是scanf(“%[^\n]”,&s),其中%[^\n]这样的表达式有点类似正则表达式的表示方式,呃题外话了,总之知道怎么样读取整行的输入,然后将字符串转化为数字,再使用邻接表建立优先关系,最后使用BFS即可。

代码如下:

#include<stdio.h>
#include<vector>
#include<queue>
#include<memory.h>
#include<cstring>
#include<iostream>
#define BOUND 10005
using namespace std;
vector<int> v[BOUND];//邻接表v[i]中存的是节点i的前趋节点 
queue<int> q;
long long t[BOUND];  //t[i]即节点i的消耗时间 
bool isv[BOUND];
int n,m;
char c,s[BOUND];
void toDigit(int index)  //将字符串转换成数字 
{
   int i=0,tmp=0;
   while(i<strlen(s) && s[i]!=' ')
    tmp=tmp*10+(s[i++]-'0');
   i++;
   t[index]=tmp;
   for(;i<strlen(s);i++)
   {
     tmp=0;
     while(i<strlen(s) && s[i]!=' ')
      tmp=tmp*10+(s[i++]-'0');
     v[index].push_back(tmp);
   }
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    while(scanf("%d",&n) && n)
    {
      scanf("%d",&m);
      scanf("%c",&c);
      for(int i=0;i<=n;++i)
       v[i].clear();
      for(int i=1;i<=n;++i)
      {
        scanf("%[^\n]",&s);
        scanf("%c",&c);
        toDigit(i);
      }
      memset(isv,0,sizeof(isv));
      long long ans=t[m];
      while(!q.empty())
       q.pop();
      q.push(m);
      isv[m]=true;
      while(!q.empty())
      {
        int qq=q.front();
        q.pop();
        for(int i=0;i<v[qq].size();++i)
        {
          int tmp=v[qq][i];
          if(isv[tmp])
           continue;
          ans+=t[tmp];
          q.push(tmp);
          isv[tmp]=true;
        }
      }
      printf("%lld\n",ans);
    }
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注