首页 > 阿里3.29笔试第二题
头像
Cpp学渣本渣
编辑于 2021-04-21 09:35
+ 关注

阿里3.29笔试第二题

#include<bits/stdc++.h>
using namespace std;
#define inf 99999999
#define N 102
int e[N][N], dis[N], visit[N];

int main(){
int test;
cin >> test;
int m, n, d;
while(test--){
cin >> m >> n >> d;
fill(e[0], e[0] + N*N, inf);
for(int i = 0; i < n; i++){
int x, y, z;
cin >> x >> y >> z;
e[x][y] = e[y][x] = z;
}
int minval = inf;
int minindex = 0;
for(int k = 0; k < m; k++){
fill(visit, visit + N, 0);
fill(dis, dis + N, inf);
dis[k] = 0;
//dij
for(int i = 0; i < m; i++){
int u = -1, min = inf;
for(int j = 0; j < m; j++){
if(!visit[j] && dis[j] < min){
min = dis[j];
u = j;
}
}
if(u != -1){
visit[u] = 1;
for(int v = 0; v < m; v++){
if(!visit[v] && e[u][v] != inf){
if(dis[u] + e[u][v] < dis[v]){
dis[v] = dis[u] + e[u][v];
}
}
}
}
}  //end dij
//处理
int cnt = 0;
for(int i = 0; i < N; i++){
if(i != k && dis[i] <= d){
cnt++;
}
}
if(cnt <= minval){
minval = cnt;
minindex = k;
}
}
cout << minindex;
}
return 0;
}

/*

1
4 4 4
0 1 3
1 2 1
2 3 1
1 3 4

*/

全部评论

(0) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

热门推荐