原题地址:点击打开链接
一开始以为是拓扑排序,因为看上去比较像,等写了一半后发现实际这题的做法和广搜是一样的。
——————正文——————
根据输入可以建立一个有向图,从目标点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); } }
******<转载说明>******
转载注明:诚实的偷包贼
原文地址:http://blog.csdn.net/fanfank/article/details/8952696
******<转载说明/>******