首页 > 代码库 > CJOI 05新年好 (最短路+枚举)
CJOI 05新年好 (最短路+枚举)
CJOI 05新年好 (最短路+枚举)
重庆城里有n个车站，m条双向公路连接其中的某些车站。每两个车站最多用一条公路连接，从任何一个车站出发都可以经过一条或者多条公路到达其他车站，但不同的路径需要花费的时间可能不同。在一条路径上花费的时间等于路径上所有公路需要的时间之和。
佳佳的家在车站1，他有五个亲戚，分别住在车站a,b,c,d,e。过年了，他需要从自己的家出发，拜访每个亲戚（顺序任意），给他们送去节日的祝福。怎样走，才需要最少的时间？
输入
第一行：n(n<=50,000),m(m<=100,000)为车站数目和公路的数目。
第二行：a,b,c,d,e，为五个亲戚所在车站编号（1<a,b,c,d,e<=n）。
以下m行，每行三个整数x,y,t（1<=x,y<=n,1<=t<=100）,为公路连接的两个车站编号和时间。
输出
仅一行，包含一个整数T，为最少的总时间
样例输入
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
样例输出
21
解题报告
必须经过a,b,c,d,e这几个点，故我们必须知道包括起点在内的6个点的最短路。所以跑6遍堆优dijkstra。最后再对a,b,c,d,e的顺序进行全排列，计算结果取最小即可。
复杂度O(6*nlogn)
#include<bits/stdc++.h>#define Pair pair<int,int>#define MAXN 70000+10#define MAXM 200000+10using namespace std;struct Edge{ int next,to,dis;}edge[MAXM];int n,m,num,v[MAXN],dis[MAXN],head[MAXN];int disi[9][MAXN],u[MAXN],ans=99999999,a[8],b[8];int temp=0;void add(int from,int to,int dis){ edge[++num].next=head[from]; edge[num].to=to; edge[num].dis=dis; head[from]=num;}void dij(int s){ memset(v,0,sizeof(v)); priority_queue<Pair,vector<Pair>,greater<Pair> > h; for(int i=1;i<=n;i++) disi[s][i]=99999999; disi[s][u[s]]=0; h.push(Pair(0,u[s])); while(h.size()>0) { int k=h.top().second;h.pop(); if(v[k]) continue; v[k]=1; for(int i=head[k];i;i=edge[i].next) if(disi[s][edge[i].to]>disi[s][k]+edge[i].dis) { disi[s][edge[i].to]=disi[s][k]+edge[i].dis; h.push(Pair(disi[s][edge[i].to],edge[i].to)); } }}void dfs(int x){ for(int i=1;i<=5;i++) if(!b[i]) { b[i]=1; a[x]=i; if(x==5) { temp=0; for(int i=0;i<5;i++) temp+=disi[a[i]][u[a[i+1]]]; ans=min(ans,temp); temp=0; }else dfs(x+1); b[i]=0; a[x]=0; } }int main(){ freopen("newyear.in","r",stdin); freopen("newyear.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=5;i++) scanf("%d",&u[i]); for(int i=1;i<=m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z); } u[0]=1; for(int i=0;i<=5;i++) dij(i); a[0]=0; dfs(1); printf("%d\n",ans); return 0;}
CJOI 05新年好 (最短路+枚举)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。