又是被创亖的一天QAQ

题目描述：王国有N个城市，编号1到N，其中有K个一线城市。王国中的所有城市由M条双向公路连接，第i条公路连接着城市ui和vi
需要ti单位时间来通过。这些公路使得王国中任何两个城市都能够通过一条或更多条公路相互到达。

王国想选一个城市作为首都，希望首都到K个一线城市的平均用时最小。请你帮忙确定一下首都是哪一个城市，如果有多个城市平均用时最小，首都将定为其中编号最小的城市。

输入格式：输入的第一行是三个整数NN, KK和MM。
接下来KK行，每行一个整数c_ic
i
​
，表示一个一线城市的编号。
再接下来的MM行，每行包含三个整数u_i, v_i, t_iu
，表示一条双向公路。
样例：13 6 15
11
13
10
12
8
1
2 4 3
7 11 3
10 11 1
4 13 3
9 10 3
2 3 2
3 5 4
5 9 2
6 7 6
5 6 1
1 2 4
4 5 3
11 12 3
6 10 1
7 8 7
输出：10

#include
using namespace std;
const int N=1005;  
int ma[N][N],name[N]; 
const int inf=1<<29; 
int main(){
    int n,k,m; 
    cin>>n>>k>>m;
    for(int i=1;i<=k;i++){
        cin>>name[i];
    }
    memset(ma,0x3f,sizeof ma);  
    for(int i=1;i<=m;i++){
    int u,v,w;
    cin>>u>>v>>w;
    ma[u][v]=ma[v][u]=min(ma[u][v],w);  
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                ma[name[j]][name[k]]=min(ma[name[j]][name[k]],ma[name[j]][name[i]]+ma[name[i]][name[k]]); 
            }
        }
    }
    int re=inf;  
    int built=0; 
    for(int i=1;i<=n;i++){
        int sum=0;
        for(int j=1;j<=n;j++){
            sum+=ma[name[i]][name[j]]; 
        }
        if(sumname[i];
        }
    }
    cout<return 0;
    }

可以说真的是检查的很仔细了，QAQ哪位大奆能帮个忙啊T……T

#include<bits/stdc++.h>
using namespace std;
const int N=1005;  
int ma[N][N],name[N]; 
const int inf=1<<29; 
int main(){
    int n,k,m; 
    cin>>n>>k>>m;
    for(int i=1;i<=k;i++){
        cin>>name[i];
    }
    memset(ma,0x3f,sizeof ma);  
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        ma[u][v]=ma[v][u]=min(ma[u][v],w);  
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                ma[j][k]=min(ma[j][k],ma[j][i]+ma[i][k]); 
            }
        }
    }
    int re=inf;  
    int built=0; 
    for(int i=1;i<=k;i++){
        int sum=0;
        for(int j=1;j<=k;j++){
            sum+=ma[name[i]][name[j]]; 
        }
        if(sum<re){ 
            re=sum;
            built=name[i];
        }
    }
    cout<<built<<endl;
    return 0;
}

这题可以用Floyd算法来求解，首先初始化一个数组，用于存储每个点的到所有一线城市的最短路径。然后再用Floyd算法更新这个数组，最后再从所有点中找出路径总和最小的一个点作为首都即可

这道题可以使用 Dijkstra 算法来解决。具体来说，对于每个城市，我们可以计算出它到所有一线城市的最短路，然后求出这些最短路的平均值，最后取平均值最小的城市作为首都。注意，这里的最短路不是单纯的距离，而是加上了通过每条公路所需要的时间。

具体的做法如下：

1.对于每个一线城市，以其为起点运行 Dijkstra 算法，计算出它到所有其他城市的最短路，这里的距离定义为通过公路所需要的时间。
2.对于每个城市，计算它到所有一线城市的最短路之和，然后除以 K，得到它到所有一线城市的平均用时。
3.找到平均用时最小的城市，输出其编号。
以下是具体的实现过程：

import heapq

INF = float('inf')

n, k, m = map(int, input().split())
first_line = [int(input()) for _ in range(k)]
graph = [[] for _ in range(n + 1)]
for _ in range(m):
    u, v, t = map(int, input().split())
    graph[u].append((v, t))
    graph[v].append((u, t))

# Dijkstra 算法求最短路
def dijkstra(src):
    dist = [INF] * (n + 1)
    dist[src] = 0
    pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, t in graph[u]:
            if dist[u] + t < dist[v]:
                dist[v] = dist[u] + t
                heapq.heappush(pq, (dist[v], v))
    return dist

# 计算所有城市到一线城市的平均用时
ans = INF
res = -1
for i in range(1, n + 1):
    dist = dijkstra(i)
    s = sum(dist[j] for j in first_line)
    if s < ans:
        ans = s
        res = i

print(res)

时间复杂度为 O(N(M+KlogN))，其中 M 是公路数，K 是一线城市数。

您的代码存在几个问题：

1、题目中只有 K 个一线城市，但是您的代码将所有城市都考虑在内了，导致时间复杂度过高。
2、在计算首都到 K 个一线城市的平均用时时，应该除以 K，而不是除以 N。
下面是修改后的代码：

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int ma[N][N],name[N];
const int inf=0x3f3f3f3f;
int main(){
int n,k,m;
cin>>n>>k>>m;
for(int i=1;i<=k;i++){
cin>>name[i];
}
memset(ma,0x3f,sizeof ma);
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
ma[u][v]=ma[v][u]=min(ma[u][v],w);
}
for(int i=1;i<=k;i++){
for(int j=1;j<=k;j++){
for(int p=1;p<=k;p++){
ma[name[j]][name[p]]=min(ma[name[j]][name[p]],ma[name[j]][name[i]]+ma[name[i]][name[p]]);
}
}
}
int re=inf, built=0;
for(int i=1;i<=k;i++){
int sum=0;
for(int j=1;j<=k;j++){
sum+=ma[name[i]][name[j]];
}
if(sum<re){
re=sum;
built=name[i];
}
}
cout<<built<<endl;
return 0;
}

有以下几点需要修改：

1.题目中的所有城市是由M条双向公路连接，第i条公路连接着城市ui和vi，表示城市ui和vi之间有一条双向公路，在代码中要注意处理。
2.初始化邻接矩阵时，要让自己到自己的距离为0，即ma[i][i]=0。
3.进行Floyd算法时，三重循环的枚举顺序要与题目描述的一致，即for(int j=1;j<=k;j++)、for(int k=1;k<=k;k++)、for(int i=1;i<=n;i++)。
4.计算平均用时时，要除以K，因为要求的是到K个一线城市的平均用时。
5.最后，要输出编号最小的城市，即built最小时的城市编号。

以下是修改后的代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1005;  
int ma[N][N]; 
const int inf=1<<29; 
int main(){
    int n,k,m; 
    cin>>n>>k>>m;
    int name[k+1];
    for(int i=1;i<=k;i++){
        cin>>name[i];
    }
    memset(ma,0x3f,sizeof ma);  
    for(int i=1;i<=n;i++){
        ma[i][i]=0;  
    }
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        ma[u][v]=ma[v][u]=min(ma[u][v],w);  
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++){
            for(int k=1;k<=k;k++){
                ma[name[j]][name

该回答引用ChatGPT
参考下面的代码

#include<bits/stdc++.h>
using namespace std;
const int N=10010,M=100010;
int n,k,m,a[N];
int f[N],g[N];
int find(int x){
    if(f[x]!=x){
        int r=find(f[x]);
        g[x]+=g[f[x]];
        f[x]=r;
    }
    return f[x];
}
bool cmp(const int &x,const int &y){
    return x<y;
}
int main(){
    cin>>n>>k>>m;
    for(int i=0;i<k;i++){
        cin>>a[i];
    }
    sort(a,a+k,cmp);
    for(int i=1;i<=n;i++){
        f[i]=i;
    }
    for(int i=0;i<m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        int fx=find(x),fy=find(y);
        if(fx!=fy){
            f[fx]=fy;
            g[fx]=g[y]+z-g[x];
        }
    }
    int ans=0x3f3f3f3f,idx=0;
    for(int i=0;i<k;i++){
        int x=a[i];
        int fx=find(x);
        if(g[x]<ans){
            ans=g[x];
            idx=fx;
        }
    }
    cout<<idx<<endl;
    return 0;
}

一个一线城市的编号。
MM行，每行包含三整数u_i, v_i, t_iu
一条双向公路。
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int ma[N][N],name[N];
const int inf=1<<29;
 
int main(){
int n,k,m;
cin>>n>>k>>m;
for(int i=1;i<=k;i++){
cin>>name[i];
}
memset(ma,0x3f,sizeof ma);
for(int i=1;i<=n;i++){
ma[i][i]=0;
}
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
ma[u][v]=ma[v][u]=min(ma[u][v],w);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int k=1;k<=n;k++){
ma[j][k]=min(ma[j][k],ma[j][i]+ma[i][k]);
}
}
}
int re=inf;
int built=0;
for(int i=1;i<=n;i++){
int sum=0;
for(int j=1;j<=k;j++){
sum+=ma[i][name[j]];
}
if(sum<re){
re=sum;
built=i;
}
}
cout<<built<<endl;
return 0;
}