开通网站后,如何建设远程教育网站,云程环境建设集团网站,怎样进入12345的公众号紧急救援
作为一个城市的应急救援队伍的负责人#xff0c;你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候#xff0c;你的任务… 紧急救援
作为一个城市的应急救援队伍的负责人你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候你的任务是带领你的救援队尽快赶往事发地同时一路上召集尽可能多的救援队。
输入格式:
输入第一行给出4个正整数N、M、S、D其中N2≤N≤500是城市的个数顺便假设城市的编号为0 ~ (N−1)M是快速道路的条数S是出发地的城市编号D是目的地的城市编号。
第二行给出N个正整数其中第i个数是第i个城市的救援队的数目数字间以空格分隔。随后的M行中每行给出一条快速道路的信息分别是城市1、城市2、快速道路的长度中间用空格分开数字均为整数且不超过500。输入保证救援可行且最优解唯一。
输出格式:
第一行输出最短路径的条数和能够召集的最多的救援队数量。第二行输出从S到D的路径中经过的城市编号。数字间以空格分隔输出结尾不能有多余空格。
输入样例:
4 5 0 3
20 30 40 10
0 1 1
1 3 2
0 3 3
0 2 2
2 3 2输出样例:
2 60
0 1 3
求路径一维数组记录即可 dfs 正着读出来
1、int father[N];
2、father[x]t father[s]-1;
3、读
void print(int x)
{if(father[s]-1){couts;return ;}print(father[x]);cout x;
}
#includeiostream
#includealgorithm
#includecstring
using namespace std;
const int N550;
int g[N][N];
int city_num[N];
int city_sum[N];
int path_num[N];
int father[N];
int dist[N];
bool st[N];
int n,m,s,d;
void dijkstra()
{memset(dist,0x3f,sizeof dist);dist[s]0;father[s]-1;city_sum[s]city_num[s];for(int i0;in;i){int t-1;for(int j0;jn;j){if(!st[j](dist[j]dist[t]||t-1)) tj;}st[t]1;for(int j0;jn;j){if(!st[j]dist[j]dist[t]g[t][j]){dist[j]dist[t]g[t][j];city_sum[j]city_sum[t]city_num[j];father[j]t;path_num[j]path_num[t];}else if(!st[j]dist[j]dist[t]g[t][j]){path_num[j]path_num[t];if(city_sum[j]city_sum[t]city_num[j]){city_sum[j]city_sum[t]city_num[j];father[j]t;}}}}
}
void print(int x)
{if(father[x]-1)//if(xs){couts;return ;}print(father[x]);cout x;
}
int main()
{cinnmsd;for(int i0;in;i){cincity_num[i];path_num[i]1;}memset(g,0x3f,sizeof g);for(int i0;in;i) g[i][i]0;while(m--){int a,b,c;cinabc;g[a][b]g[b][a]min(g[a][b],c);}dijkstra();coutpath_num[d] city_sum[d]endl;print(d);return 0;
} 迷宫问题
给定一个 n×n的二维数组如下所示
int maze[5][5] {0, 1, 0, 0, 0,0, 1, 0, 1, 0,0, 0, 0, 0, 0,0, 1, 1, 1, 0,0, 0, 0, 1, 0,};它表示一个迷宫其中的1表示墙壁0表示可以走的路只能横着走或竖着走不能斜着走要求编程序找出从左上角到右下角的最短路线。
数据保证至少存在一条从左上角走到右下角的路径。
输入格式
第一行包含整数 n。
接下来 n 行每行包含 n 个整数 0 或 1表示迷宫。
输出格式
输出从左上角到右下角的最短路线如果答案不唯一输出任意一条路径均可。
按顺序每行输出一个路径中经过的单元格的坐标左上角坐标为 (0,0)(0,0)右下角坐标为 (n−1,n−1)。
数据范围
0≤n≤1000
输入样例
5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0输出样例
0 0
1 0
2 0
2 1
2 2
2 3
2 4
3 4
4 4 求路劲坐标用pair存储 二维数组表示出来x,y的下一个点
1、定义
typedef pairint,intPII;
PII pre[N][N];
2、表示
{pre[0][0]{-1,-1}//起点的前驱PII tq.front();pre[x][y]t;
}
3、输出 可以用dfs/或者在存的时候直接倒着存
void print(int x,int y)
{if(pre[x][y]PII{-1,-1}){cout0 0endl;}print(pre[x][y].frist,pre[x][y].second);coutx yendl;
}#includeiostream
#includequeue
#includealgorithm
#define x first
#define y second
using namespace std;
typedef pairint,intPII;
const int N1010;
int g[N][N];
bool st[N][N];//标记数组 表示当前位置是否走过
PII pre[N][N];//存储当前位置的前驱
int dx[4]{0,0,-1,1},dy[4]{1,-1,0,0};
int n;
void bfs()
{queuePIIq;//为了正着写位置方便 倒这遍历到00 在从00输出pre数组q.push({n-1,n-1});st[n-1][n-1]true;while(q.size()){PII tq.front();q.pop();for(int i0;i4;i){int x1t.xdx[i],y1t.ydy[i];if(x10||x1n||y10||y1n) continue;//越界if(st[x1][y1]) continue;//已走过if(g[x1][y1]) continue;//是墙 无法走q.push({x1,y1});st[x1][y1]true;pre[x1][y1]t;//标记当前位置的前驱}}
}
int main()
{scanf(%d,n);for(int i0;in;i)for(int j0;jn;j)scanf(%d,g[i][j]);bfs();
//PII end{0,0};PII end(0,0);while(1){printf(%d %d\n,end.x,end.y);if(end.xn-1end.yn-1) break;endpre[end.x][end.y];}return 0;
} 魔板
Rubik 先生在发明了风靡全球的魔方之后又发明了它的二维版本——魔板。
这是一张有 88 个大小相同的格子的魔板
1 2 3 4
8 7 6 5我们知道魔板的每一个方格都有一种颜色。
这 88 种颜色用前 88 个正整数来表示。
可以用颜色的序列来表示一种魔板状态规定从魔板的左上角开始沿顺时针方向依次取出整数构成一个颜色序列。
对于上图的魔板状态我们用序列 (1,2,3,4,5,6,7,8)(1,2,3,4,5,6,7,8) 来表示这是基本状态。
这里提供三种基本操作分别用大写字母 ABC 来表示可以通过这些操作改变魔板的状态
A交换上下两行 B将最右边的一列插入到最左边 C魔板中央对的4个数作顺时针旋转。
下面是对基本状态进行操作的示范
A
8 7 6 5
1 2 3 4B
4 1 2 3
5 8 7 6C
1 7 2 4
8 6 3 5对于每种可能的状态这三种基本操作都可以使用。
你要编程计算用最少的基本操作完成基本状态到特殊状态的转换输出基本操作序列。
注意数据保证一定有解。
输入格式
输入仅一行包括 88 个整数用空格分开表示目标状态。
输出格式
输出文件的第一行包括一个整数表示最短操作序列的长度。
如果操作序列的长度大于0则在第二行输出字典序最小的操作序列。
数据范围
输入数据中的所有数字均为 11 到 88 之间的整数。
输入样例
2 6 8 4 5 7 3 1输出样例
7
BCABCCB 求步骤一种状态到另一种状态中有步骤代替
#includeunordered_map
1、unordered_mapstring,pairchar,stringpre
2、 pre[x]{Ai,t};
3、 while(1){if(end12345678) break;spre[end].first;endpre[end].second;}reverse(s.begin(),s.end()); #includeiostream
#includequeue
#includealgorithm
#define x first
#define y second
using namespace std;
typedef pairint,intPII;
const int N1010;
int g[N][N];
bool st[N][N];//标记数组 表示当前位置是否走过
PII pre[N][N];//存储当前位置的前驱
int dx[4]{0,0,-1,1},dy[4]{1,-1,0,0};
int n;
void bfs()
{queuePIIq;//为了正着写位置方便 倒这遍历到00 在从00输出pre数组q.push({n-1,n-1});st[n-1][n-1]true;while(q.size()){PII tq.front();q.pop();for(int i0;i4;i){int x1t.xdx[i],y1t.ydy[i];if(x10||x1n||y10||y1n) continue;//越界if(st[x1][y1]) continue;//已走过if(g[x1][y1]) continue;//是墙 无法走q.push({x1,y1});st[x1][y1]true;pre[x1][y1]t;//标记当前位置的前驱}}
}
int main()
{scanf(%d,n);for(int i0;in;i)for(int j0;jn;j)scanf(%d,g[i][j]);bfs();
//PII end{0,0};PII end(0,0);while(1){printf(%d %d\n,end.x,end.y);if(end.xn-1end.yn-1) break;endpre[end.x][end.y];}return 0;
}
