重庆城里有n个车站,m条双向公路连接其中的某些站。每两个车站最多用一条公路直接相连,从任何一个车站出发都可以经过一条或多条公路到达其它车站,但不同的路径需要花费的时间可能不同。在一条路径上花费的时间等于路径上所有公路需要的时间和。
佳佳的家在车站1,他有五个亲戚,分别住在车站a、b、c、d、e。过年了,他需要从自己的家出发,拜访每个亲戚(顺序任意),给他们送去节日的祝福。怎样走,才需要最少的时间?
用最短路算法,求出5个点分别的距离,和1到五个点的距离,
然后枚举完事
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<cstdio> #include<cstdlib> #include<cstring> #include<queue> using namespace std; int n,m; const int N=5e4+3,M=1e5+3; int tot,head[N]; struct node { int v,w,nx; }e[M<<1]; void add(int u,int v,int w) { e[++tot].v =v,e[tot].w =w,e[tot].nx =head[u],head[u]=tot; e[++tot].v =u,e[tot].w =w,e[tot].nx =head[v],head[v]=tot; } inline int read() { int x=0;char c=getchar(); while(c<'0' || c>'9') c=getchar(); while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar(); return x; } int dis[N]; bool in[N]; int pt[6],dd[6][6]; struct nd { int v; bool operator < (const nd & o) const { return dis[v] > dis[o.v]; } nd(int vv) { v=vv; } nd(){} }; priority_queue <nd> q; void dijk(int st,int k) { while(!q.empty() ) q.pop() ; memset(dis,0x3f,sizeof(dis)); memset(in,false,sizeof(in)); dis[st]=0,q.push(nd(st)); while(!q.empty() ) { int nw=q.top() .v;q.pop() ; for(int i=head[nw];i;i=e[i].nx ) { int nx=e[i].v ; if(dis[nx]>dis[nw]+e[i].w ) { dis[nx]=dis[nw]+e[i].w ; if(!in[nx]) in[nx]=true,q.push(nd(nx)); } } in[nw]=false; } for(int i=1;i<=5;i++) dd[k][i]=dis[pt[i]]; } bool us[6];int ans=1<<30; void dfs(int cnt,int sum,int pre) { if(sum>ans) return ; if(cnt==5) { ans=min(ans,sum); return ; } for(int i=1;i<=5;i++) { if(us[i]) continue; us[i]=true; dfs(cnt+1,sum+dd[pre][i],i); us[i]=false; } } int main() { n=read(),m=read(); pt[0]=1; for(int i=1;i<=5;i++) scanf("%d",&pt[i]); int u,v,w; for(int i=1;i<=m;i++) { u=read(),v=read(),w=read(); add(u,v,w); } for(int i=0;i<=5;i++) dijk(pt[i],i); dfs(0,0,0); printf("%d ",ans); return 0; }