建设体育课程基地网站,淘宝店铺可以做网站优化么,广州传业建设有限公司网站,邦策网站建设平台作为一个城市的应急救援队伍的负责人#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搜索全部情况返回最优解
#includebits/stdc.h
using namespace std;
const int maxn 510;
int N, M, S, D, A, B, C, road 0, love, mind 1 20;//路径 救援数
vectorintsove(maxn);
int MAP[maxn][maxn];
dequeintans;
dequeints;
bool vis[maxn][maxn];
void DFS(int str, int end, int d, int sum)//起始 结尾 路径 救援数
{if (str end mind d){ //达到目的地 if(mind d){road 0;ans s;mind d;love sum;}else if(d mind love sum){love sum;ans s;}road;return;}else if(str end)return;for (int i 0; i N; i){if (MAP[str][i] !vis[str][i]){vis[str][i] true;s.push_back(i);DFS(i, end, d MAP[str][i], sum sove[i]);vis[str][i] false;s.pop_back();}}
}int main()
{cin N M S D;for (int i 0; i N; i){cin sove[i];}for (int i 0; i M; i){cin A B C;MAP[A][B] MAP[B][A] C;}DFS(S, D, 0, sove[S]);cout road love endl S;while (!ans.empty()){cout ans.front();ans.pop_front();}return 0;
}
但是缺陷也是比较明显的,如果图中各节点的联通网十分密集的话,那我们递归的深度就很容易导致系统栈被压爆,从而得不出答案 那么就得涉及到最短路径算法了,常见的Dijkstra或者Floyd
当然也有Bellman 和 SPFA但是对于这题效果不如dijkstra
简单的科普Dijkstra和Floyd算法
最短路径Dijkstra算法和Floyd算法_法苏ovo的博客-CSDN博客
基于Floyd大多是处理任意俩点最短路径(并且效率较低)而我们这题侧重于单源路径,就采用Dijikstra进行解题
#include bits/stdc.h
#define endl \n
using namespace std;
const int maxn 510;
int N, M, S, D, A, B, len;
vectorintp(maxn), pre(maxn, -1), num(maxn), per(maxn), dis(maxn, INT_MAX);
// 各点的救援队数量 前置结点 从起点到该点的最短路数量 从起点到该点最短路的救援队数量 从起点到该点的最短距离
bool vis[maxn];
struct edge
{int to, len;edge(int a, int b) : to(a), len(b) {};
};
vectoredgee[maxn];
struct q_node
{int id, dis;q_node(int a, int b) :id(a), dis(b) {};bool operator (const q_node s)const{return dis s.dis;}
};
void printf_path(int x)
{if (pre[x] -1) return;printf_path(pre[x]);printf( %d, x);
}
void dijkstra()
{dis[S] 0, num[S] 1, per[S] p[S];priority_queueq_nodeQ;Q.emplace(S, dis[S]);while (!Q.empty()){auto x Q.top();Q.pop();if (vis[x.id])continue;vis[x.id] true;for (int i 0; i e[x.id].size(); i){auto y e[x.id][i];//枚举邻居if (dis[y.to] dis[x.id] y.len)num[y.to] num[x.id];if (dis[y.to] dis[x.id] y.len)num[y.to] num[x.id];if ((dis[y.to] dis[x.id] y.len per[y.to] per[x.id] p[y.to]) || dis[y.to] dis[x.id] y.len){per[y.to] per[x.id] p[y.to];pre[y.to] x.id;dis[y.to] dis[x.id] y.len;Q.emplace(y.to, dis[y.to]);}}}
}
int main()
{cin N M S D;for (int i 0; i N; i)cin p[i];while (M--){cin A B len;e[A].emplace_back(B, len);e[B].emplace_back(A, len);}dijkstra();cout num[D] per[D] endl S;printf_path(D);return 0;
}
Dijkstra算法练习
公交线路 (nowcoder.com)
#includebits/stdc.h
using namespace std;
const int maxn 1010;
int n,m,s,t,A,B,len;
struct edge
{int form,to,len;edge(int a,int b,int c) : form(a),to(b),len(c){};
};
vectoredgee[maxn];
vectorintdis(maxn,0x3f3f3f3f),pre(maxn);
bool vis[maxn];
struct q_node
{int id,dis;q_node(int a,int b):id(a),dis(b){};bool operator (const q_node s)const{return dis s.dis;}
};
void dijkstra()
{dis[s] 0;priority_queueq_nodeQ;Q.emplace(s,dis[s]);while(!Q.empty()){auto x Q.top();Q.pop();if(vis[x.id])continue;vis[x.id] true;for(int i 0;i e[x.id].size();i){auto y e[x.id][i];if(vis[y.to])continue;if(dis[y.to] x.dis y.len){dis[y.to] x.dis y.len;pre[y.to] x.id;Q.emplace(y.to,dis[y.to]);}}}
}
int main()
{cin.tie(0)-sync_with_stdio(false);cin n m s t;while(m--){cin A B len;e[A].emplace_back(A,B,len);e[B].emplace_back(B,A,len);}dijkstra();dis[t] 0x3f3f3f3f ? cout -1 endl : cout dis[t] endl;return 0;
}
