3 条题解
-
2
這道題非常簡單，首先只有 個人需要拜訪，所以我們需要找到一個順序，然後使得我們走的路最少，那麼我們就可以對於每一個要拜訪的點為起點然後跑dijkstra，記錄任意兩個要拜訪的點的最小長度，枚舉累加即可
#include<iostream> #include<cstring> #include<cstdio> #include<queue> #include<map> #define int long long using namespace std; bool Test_MLE_start; constexpr int N=1e5+10; int _=1,n,m,x[6],tot=0,ans=2e9,head[N],dis[N];bool vis[N]; struct edge{int v,w,nxt;}a[N<<1];priority_queue<pair<int,int> >q;map<pair<int,int>,int> mp; inline int reads(){ char c=getchar(); int sum=0,f=1; while(!isdigit(c)){ if(c=='-') f=-1; c=getchar(); } while(isdigit(c)){ sum=(sum<<3)+(sum<<1)+(c^'0'); c=getchar(); } return sum*f; } inline void files(){ freopen("A.in","r",stdin); // freopen("std.out","w",stdout); } inline void clr(){ // Don't forget! } void add(int u,int v,int w){ a[++tot].v=v;a[tot].w=w; a[tot].nxt=head[u]; head[u]=tot; } void dijkstra(int s){ memset(dis,0x3f,sizeof(dis));memset(vis,0,sizeof(vis)); q.push(make_pair(0,s));dis[s]=0; while(!q.empty()){ int u=q.top().second;q.pop(); if(vis[u]) continue;vis[u]=1; for(int i=head[u];i;i=a[i].nxt){ int v=a[i].v; if(dis[v]>dis[u]+a[i].w) dis[v]=dis[u]+a[i].w,q.push(make_pair(-dis[v],v)); } } } bool Test_MLE_end; signed main(){ // printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0); // files(); // _=reads(); while(_--){ clr();n=reads(),m=reads();x[0]=1;for(int i=1;i<=5;i++) x[i]=reads(); for(int i=1;i<=m;i++){ int u,v,w;u=reads(),v=reads(),w=reads(); add(u,v,w),add(v,u,w); } for(int i=0;i<=5;i++){ dijkstra(x[i]); for(int j=0;j<=5;j++){ mp[make_pair(i,j)]=dis[x[j]]; } }bool flg=0; for(int A=1;A<=5;A++){ for(int B=1;B<=5;B++){ if(A==B) continue; for(int C=1;C<=5;C++){ if(B==C||C==A) continue; for(int D=1;D<=5;D++){ if(C==D||D==B||D==A) continue; for(int E=1;E<=5;E++){ if(D==E||E==C||E==B||E==A) continue; ans=min(ans,mp[make_pair(0,A)]+mp[make_pair(A,B)]+mp[make_pair(B,C)]+mp[make_pair(C,D)]+mp[make_pair(D,E)]); } } } } }printf("%lld\n",ans); } return 0; } -
0
InnitTimmer LV 8 @ 2025-9-6 17:49:18
This question is very simple. Firstly, there are only people to visit, so we need to find an order that minimizes the distance we need to walk. Then we can start from each point we want to visit and run dijkstra，Record the minimum length of any two points to be visited, enumerate and accumulate them.
#include<iostream> #include<cstring> #include<cstdio> #include<queue> #include<map> #define int long long using namespace std; bool Test_MLE_start; constexpr int N=1e5+10; int _=1,n,m,x[6],tot=0,ans=2e9,head[N],dis[N];bool vis[N]; struct edge{int v,w,nxt;}a[N<<1];priority_queue<pair<int,int> >q;map<pair<int,int>,int> mp; inline int reads(){ char c=getchar(); int sum=0,f=1; while(!isdigit(c)){ if(c=='-') f=-1; c=getchar(); } while(isdigit(c)){ sum=(sum<<3)+(sum<<1)+(c^'0'); c=getchar(); } return sum*f; } inline void files(){ freopen("A.in","r",stdin); // freopen("std.out","w",stdout); } inline void clr(){ // Don't forget! } void add(int u,int v,int w){ a[++tot].v=v;a[tot].w=w; a[tot].nxt=head[u]; head[u]=tot; } void dijkstra(int s){ memset(dis,0x3f,sizeof(dis));memset(vis,0,sizeof(vis)); q.push(make_pair(0,s));dis[s]=0; while(!q.empty()){ int u=q.top().second;q.pop(); if(vis[u]) continue;vis[u]=1; for(int i=head[u];i;i=a[i].nxt){ int v=a[i].v; if(dis[v]>dis[u]+a[i].w) dis[v]=dis[u]+a[i].w,q.push(make_pair(-dis[v],v)); } } } bool Test_MLE_end; signed main(){ // printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0); // files(); // _=reads(); while(_--){ clr();n=reads(),m=reads();x[0]=1;for(int i=1;i<=5;i++) x[i]=reads(); for(int i=1;i<=m;i++){ int u,v,w;u=reads(),v=reads(),w=reads(); add(u,v,w),add(v,u,w); } for(int i=0;i<=5;i++){ dijkstra(x[i]); for(int j=0;j<=5;j++){ mp[make_pair(i,j)]=dis[x[j]]; } }bool flg=0; for(int A=1;A<=5;A++){ for(int B=1;B<=5;B++){ if(A==B) continue; for(int C=1;C<=5;C++){ if(B==C||C==A) continue; for(int D=1;D<=5;D++){ if(C==D||D==B||D==A) continue; for(int E=1;E<=5;E++){ if(D==E||E==C||E==B||E==A) continue; ans=min(ans,mp[make_pair(0,A)]+mp[make_pair(A,B)]+mp[make_pair(B,C)]+mp[make_pair(C,D)]+mp[make_pair(D,E)]); } } } } }printf("%lld\n",ans); } return 0; }
- 1
