一般做网站费用,360营销推广,旅游平台网站建设方案,网站的做用吝啬的国度 时间限制#xff1a;1000 ms | 内存限制#xff1a;65535 KB难度#xff1a;3描写叙述在一个吝啬的国度里有N个城市。这N个城市间仅仅有N-1条路把这个N个城市连接起来。如今#xff0c;Tom在第S号城市#xff0c;他有张该国地图。他想知道如果自己要去參观第… 吝啬的国度 时间限制1000 ms | 内存限制65535 KB 难度3 描写叙述在一个吝啬的国度里有N个城市。这N个城市间仅仅有N-1条路把这个N个城市连接起来。如今Tom在第S号城市他有张该国地图。他想知道如果自己要去參观第T号城市。必须经过的前一个城市是几号城市如果你不走反复的路。 输入第一行输入一个整数M表示測试数据共同拥有M(1M5)组 每组測试数据的第一行输入一个正整数N(1N100000)和一个正整数S(1S100000)。N表示城市的总个数S表示參观者所在城市的编号 随后的N-1行。每行有两个正整数a,b(1a,bN)表示第a号城市和第b号城市之间有一条路连通。输出每组測试数据输N个正整数当中。第i个数表示从S走到i号城市必需要经过的上一个城市的编号。当中iS时请输出-1例子输入 1
10 1
1 9
1 8
8 10
10 3
8 6
1 2
10 4
9 5
3 7例子输出 -1 1 10 10 9 8 3 1 1 8解题思路 一開始用了队列来求起点入队。然后出队。找到跟起点相连的城市进队那么这些城市的前一步就是出队的城市了然后開始不停地出队入队直到队空为止。思路不错。可是超时了。 经过看大神的代码发现这个题能够用深搜来解决再一看题目发现这确实符合深搜的特性。 无论是队列还是深搜都须要标记。 队列用到了#includequeueSTL函数 #include iostream
#include queue
using namespace std; //这几个头文件不可缺少int main()
{
queue类型如int q; //使用前需定义一个queue变量且定义时已经初始化
while(!q.empty()) q.pop(); //反复使用时用这个初始化空则返回1不空返回0
q.push(1); //进队列
q.pop(); //出队列
int vq.front(); //得到队首的值
int sq.size(); //得到队列里元素个数return 0;
} 由于给定的城市N的数目太大建立数组须要用到#includevectorvector就是一个不定长数组vectorinta就是一个类似于int a[]的整数数组仅仅只是他的长度不确定。能够用a.size()读取他的长度。 而vectorinta[max]就是一个二维数组仅仅是第一维的大小是固定的不超过max二维的大小就不固定了这道题之所以用到vector就是利用了他的不定长假设直接建立二维数组a[n][n]。n太大了这种二维数组绝对超出内存。 (1)头文件#includevector. (2)创建vector对象vectorint vec; (3)尾部插入数字vec.push_back(a); (4)使用下标訪问元素。coutvec[0]endl;记住下标是从0開始的。 (5)向量大小:vec.size(); 代码 //队列思路超时
#includestdio.h
#includestring.h
#includeiostream
#includequeue
using namespace std;
int sta[110000];
int map[110000][3];
int ans[110000];
int main()
{int m;int n,s;int i,j,k;int now;queueintq;scanf(%d,m);while(m--){scanf(%d%d,n,s);q.push(s);for(i1;in;i){map[i][0]1;scanf(%d%d,map[i][1],map[i][2]);}memset(ans,0,sizeof(ans));ans[s]-1;while(!q.empty()){nowq.front();q.pop();for(i1;in;i){if(map[i][0]map[i][1]now){q.push(map[i][2]);ans[map[i][2]]now;map[i][0]0;}else if(map[i][0]map[i][2]now){q.push(map[i][1]);ans[map[i][1]]now;map[i][0]0;}}}for(i1;in;i){printf(%d,ans[i]);if(i!n)printf( );elseprintf(\n);}}return 0;
}
//深搜代码AC
#includestdio.h
#includestring.h
#includeiostream
#includevector
#includealgorithm
using namespace std;
int pre[100005];
vectorintv[100005];void dfs(int s)
{int i;for(i0;iv[s].size();i){if(pre[v[s][i]])continue;pre[v[s][i]]s;dfs(v[s][i]);}
}
int main()
{int m;int n,s;int a,b;int i,j;scanf(%d,m);while(m--){memset(v,0,sizeof(v));memset(pre,0,sizeof(pre));scanf(%d%d,n,s);pre[s]-1;for(i0;in-1;i){scanf(%d%d,a,b);v[a].push_back(b);v[b].push_back(a);}dfs(s);for(i1;in;i){printf(%d,pre[i]);if(i!n)printf( );elseprintf(\n);}}return 0;
}转载于:https://www.cnblogs.com/brucemengbm/p/6892334.html
