高青网站建设,网站dedecms数据库,网站建设对企业很重要,公司网站建设需要显示什么P5764 [CQOI2005]新年好
题目描述
重庆城里有 nnn 个车站#xff0c;mmm 条双向公路连接其中的某些车站。每两个车站最多用一条公路连接#xff0c;从任何一个车站出发都可以经过一条或者多条公路到达其他车站#xff0c;但不同的路径需要花费的时间可能不同。在一条路径上…P5764 [CQOI2005]新年好
题目描述
重庆城里有 nnn 个车站mmm 条双向公路连接其中的某些车站。每两个车站最多用一条公路连接从任何一个车站出发都可以经过一条或者多条公路到达其他车站但不同的路径需要花费的时间可能不同。在一条路径上花费的时间等于路径上所有公路需要的时间之和。
佳佳的家在车站 111他有五个亲戚分别住在车站 a,b,c,d,ea,b,c,d,ea,b,c,d,e。过年了他需要从自己的家出发拜访每个亲戚顺序任意给他们送去节日的祝福。怎样走才需要最少的时间
输入格式
第一行n,mn,mn,m分别为车站数目和公路的数目。
第二行a,b,c,d,ea,b,c,d,ea,b,c,d,e分别为五个亲戚所在车站编号。
以下 mmm 行每行三个整数 x,y,tx,y,tx,y,t为公路连接的两个车站编号和时间。
输出格式
仅一行包含一个整数 TTT为最少的总时间。保证 T≤109T\le 10^9T≤109。
样例 #1
样例输入 #1
6 6
2 3 4 5 6
1 2 8
2 3 3
3 4 4
4 5 5
5 6 2
1 6 7样例输出 #1
21提示
对于 40%40\%40% 的数据有 1≤n≤5001≤n≤5001≤n≤5001≤m≤20001≤m≤20001≤m≤2000。
对于 100%100\%100% 的数据有 1≤n≤500001≤n≤500001≤n≤500001≤m≤1000001≤m≤1000001≤m≤1000001≤a,b,c,d,e≤n1\le a,b,c,d,e≤n1≤a,b,c,d,e≤n1≤x,y≤n1≤x,y≤n1≤x,y≤n1≤t≤100001≤t≤100001≤t≤10000。
思路
起点确定所到达的点集有限且大小固定为5非常小于是我们可以爆搜访问点集中每个点的顺序也就是全排列。在爆搜过程中我们需要知道当前点xxx到要访问的点yyy的最短距离最短距离可以用很多算法求解本题数据量可知所给出的图为稀疏图范围比较大首选堆优化的Dijkstra算法最短距离需要预先处理这样在爆搜的过程中离线查询即可。本题的存图方式比较常规但是记录最短路有些讲究我们需要开一个二维数组dist[7][N]dist[7][N]dist[7][N]dist[i][j]dist[i][j]dist[i][j]表示start[i]start[i]start[i]到jjj的最短路这样记录最短路的话我们可以枚举会访问六个点到其他点的最短路。
参考代码C
#include iostream
#include cstring
#include algorithm
#include queue#define x first
#define y secondusing namespace std;typedef pairint, int PII;const int N 50010, M 200010, INF 0x3f3f3f3f;int n, m, res;
int start[7], dist[7][N];
int h[N], e[M], ne[M], w[M], idx;
bool st[N], vis[6];void add(int a, int b, int c) {e[idx] b, ne[idx] h[a], w[idx] c, h[a] idx ;
}void dijkstra(int sr, int dist[]) {memset(st, 0, sizeof st);priority_queuePII, vectorPII, greaterPII que;dist[sr] 0;que.push({0, sr});while(que.size()) {auto tt que.top(); que.pop();if(st[tt.y]) continue;st[tt.y] true;for(int i h[tt.y]; ~i; i ne[i]) {int j e[i];if(dist[j] tt.x w[i]) {dist[j] tt.x w[i];que.push({dist[j], j});}}}
}void dfs(int u, int cost, int p) {if(u 6) {res min(res, cost);}if(cost res) return ;for(int i 2; i 6; i ) {if(!vis[i]) {vis[i] true;dfs(u 1, cost dist[p][start[i]], i);vis[i] false;}}
}int main() {scanf(%d%d, n, m);start[1] 1;for(int i 2; i 6; i ) scanf(%d, start[i]);memset(h, -1, sizeof h);while(m --) {int a, b, c;scanf(%d%d%d, a, b, c);add(a, b, c), add(b, a, c);}memset(dist, 0x3f, sizeof dist);for(int i 1; i 6; i ) dijkstra(start[i], dist[i]);res INF;dfs(1, 0, 1);printf(%d\n, res);return 0;
}疑问
有疑问欢迎私信或者评论看到消息会解答
