阿里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
*/
#阿里巴巴##笔试题目#
查看19道真题和解析
