核心代码
1
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstring>
#define R 6371.004 //平均半径
#define SUP 100000000
using namespace std;
struct city{
string name;
double longitude,latitude;
};
struct edge{
int from,to;
double val;
};
double rad(double angle){return angle * M_PI / 180;}
double earth_dist(city *pos_a, city *pos_b){
double long_a = rad(pos_a->longitude);double lat_a = rad(pos_a->latitude);
double long_b = rad(pos_b->longitude);double lat_b = rad(pos_b->latitude);
double c = sin(lat_a) * sin(lat_b) + cos(lat_a) * cos(lat_b) * cos(long_b - long_a);
return R * acos(c);
}
city c[50];
double graph[50][50] = {SUP};
int visit[50] = {0};
int n = 0;
edge choose[50], low_cost[50];
int main() {
ifstream fin("data.txt");
while (!fin.eof()){
fin>>c[n].name>>c[n].longitude>>c[n].latitude;
n++;
}
fin.close();
//Build
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(i == j) graph[i][j] = 0;
else {
double dist = earth_dist(&c[i], &c[j]);
graph[i][j] = dist;graph[j][i] = dist;
}
}
}
int last_vis;
int cnt=0;int flag=0;
for(int i = 0; i < n; i++)low_cost[i] = {-1, -1, SUP};
visit[0] = 1;
last_vis = 0;
while (!flag){
flag = 1;
//Update
for(int i = 0; i < n; i++){
if(visit[i] == 0 && graph[last_vis][i] < low_cost[i].val){
low_cost[i].from = last_vis;
low_cost[i].to = i;
low_cost[i].val = graph[last_vis][i];
}
}
int min_edge_idx = -1;
double min_edge_dist = SUP;
//Search
for (int i = 0; i < n; i++) {
if(low_cost[i].val != -1.0 && low_cost[i].val < min_edge_dist){
min_edge_dist = low_cost[i].val;
min_edge_idx = i;
}
}
choose[cnt] = low_cost[min_edge_idx];
visit[min_edge_idx] = 1;
low_cost[min_edge_idx] = {-1, -1, -1.0};
last_vis = min_edge_idx;
cnt++;
for(int i = 0; i < n; i++){
if(visit[i] == 0){
flag = 0;
break;
}
}
}
double sum = 0.0;
for(int i = 0; i < cnt; i++){
cout<<c[choose[i].from].name<<"<>"<<c[choose[i].to].name<<" "<<choose[i].val<<"KM"<<endl;
sum += choose[i].val;
}
/*
for(int i = 0; i < cnt; i++){
cout<<"('"<<c[choose[i].from].name<<"','"<<c[choose[i].to].name<<"',"<<choose[i].val<<"),"<<endl;
}
*/
cout<<"SUM LEN: "<<sum<<"km"<<endl;
return 0;
}
2
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstring>
#define R 6371.004 //平均半径
#define SUP 100000000
using namespace std;
struct city{
string name;
double longitude,latitude;
};
struct edge{
int from,to;
double val;
};
double rad(double angle){return angle * M_PI / 180;}
double earth_dist(city *pos_a, city *pos_b){
double long_a = rad(pos_a->longitude);double lat_a = rad(pos_a->latitude);
double long_b = rad(pos_b->longitude);double lat_b = rad(pos_b->latitude);
double c = sin(lat_a) * sin(lat_b) + cos(lat_a) * cos(lat_b) * cos(long_b - long_a);
return R * acos(c);
}
city c[50];
double graph[50][50] = {SUP};
int visit[50] = {0};
int n = 0;
edge choose[50], low_cost[50];
int main() {
int xi_ning_idx, zheng_zhou_idx;
ifstream fin("data.txt");
while (!fin.eof()){
fin>>c[n].name>>c[n].longitude>>c[n].latitude;
if (c[n].name == "西宁市") xi_ning_idx = n;
else if (c[n].name == "郑州市") zheng_zhou_idx = n;
n++;
}
fin.close();
//Build
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(i == j) graph[i][j] = 0;
else {
double dist = earth_dist(&c[i], &c[j]);
graph[i][j] = dist;graph[j][i] = dist;
}
}
}
int last_vis;
int cnt=0;int flag=0;
for(int i = 0; i < n; i++)low_cost[i] = {-1, -1, SUP};
choose[0].from = xi_ning_idx;
choose[0].to = zheng_zhou_idx;
choose[0].val = graph[xi_ning_idx][zheng_zhou_idx];
++cnt;
visit[xi_ning_idx] = 1;
visit[zheng_zhou_idx] = 1;
last_vis = xi_ning_idx;
for(int i = 0; i < n; i++){
if(visit[i] == 0 && graph[last_vis][i] < low_cost[i].val){
low_cost[i].from = last_vis;
low_cost[i].to = i;
low_cost[i].val = graph[last_vis][i];
}
}
last_vis = zheng_zhou_idx;
while (!flag){
flag = 1;
//Update
for(int i = 0; i < n; i++){
if(visit[i] == 0 && graph[last_vis][i] < low_cost[i].val){
low_cost[i].from = last_vis;
low_cost[i].to = i;
low_cost[i].val = graph[last_vis][i];
}
}
int min_edge_idx = -1;
double min_edge_dist = SUP;
//Search
for (int i = 0; i < n; i++) {
if(low_cost[i].val != -1.0 && low_cost[i].val < min_edge_dist){
min_edge_dist = low_cost[i].val;
min_edge_idx = i;
}
}
choose[cnt] = low_cost[min_edge_idx];
visit[min_edge_idx] = 1;
low_cost[min_edge_idx] = {-1, -1, -1.0};
last_vis = min_edge_idx;
cnt++;
for(int i = 0; i < n; i++){
if(visit[i] == 0){
flag = 0;
break;
}
}
}
double sum = 0.0;
for(int i = 0; i < cnt; i++){
cout<<c[choose[i].from].name<<"<>"<<c[choose[i].to].name<<" "<<choose[i].val<<"KM"<<endl;
sum += choose[i].val;
}
/*
for(int i = 0; i < cnt; i++){
cout<<"('"<<c[choose[i].from].name<<"','"<<c[choose[i].to].name<<"',"<<choose[i].val<<"),"<<endl;
}
*/
cout<<"SUM LEN: "<<sum<<"km"<<endl;
return 0;
}
3
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstring>
#define R 6371.004 //平均半径
#define SUP 100000000
using namespace std;
struct city{
string name;
double longitude,latitude;
};
struct edge{
int from,to;
double val;
};
double rad(double angle){return angle * M_PI / 180;}
double earth_dist(city *pos_a, city *pos_b){
double long_a = rad(pos_a->longitude);double lat_a = rad(pos_a->latitude);
double long_b = rad(pos_b->longitude);double lat_b = rad(pos_b->latitude);
double c = sin(lat_a) * sin(lat_b) + cos(lat_a) * cos(lat_b) * cos(long_b - long_a);
return R * acos(c);
}
city c[50];
double graph[50][50] = {SUP};
int visit[50] = {0};
int n = 0;
edge choose[50], low_cost[50];
int main() {
int xi_ning_idx, zheng_zhou_idx,hang_zhou_idx, chang_sha_idx;
ifstream fin("data.txt");
while (!fin.eof()){
fin>>c[n].name>>c[n].longitude>>c[n].latitude;
if (c[n].name == "西宁市") xi_ning_idx = n;
else if (c[n].name == "郑州市") zheng_zhou_idx = n;
else if (c[n].name == "杭州市") hang_zhou_idx = n;
else if (c[n].name == "长沙市") chang_sha_idx = n;
n++;
}
fin.close();
//Build
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(i == j) graph[i][j] = 0;
else {
double dist = earth_dist(&c[i], &c[j]);
graph[i][j] = dist;graph[j][i] = dist;
}
}
}
int last_vis;
int cnt=0;int flag=0;
for(int i = 0; i < n; i++)low_cost[i] = {-1, -1, SUP};
choose[0].from = xi_ning_idx;
choose[0].to = zheng_zhou_idx;
choose[0].val = graph[xi_ning_idx][zheng_zhou_idx];
++cnt;
visit[xi_ning_idx] = 1;
visit[zheng_zhou_idx] = 1;
last_vis = xi_ning_idx;
for(int i = 0; i < n; i++){
if(visit[i] == 0 && graph[last_vis][i] < low_cost[i].val){
low_cost[i].from = last_vis;
low_cost[i].to = i;
low_cost[i].val = graph[last_vis][i];
}
}
last_vis = zheng_zhou_idx;
while (!flag){
flag = 1;
//Update
for(int i = 0; i < n; i++){
if(visit[i] == 0 && graph[last_vis][i] < low_cost[i].val){
low_cost[i].from = last_vis;
low_cost[i].to = i;
low_cost[i].val = graph[last_vis][i];
}
}
int min_edge_idx = -1;
double min_edge_dist = SUP;
//Search
for (int i = 0; i < n; i++) {
if(low_cost[i].val != -1.0 && low_cost[i].val < min_edge_dist){
min_edge_dist = low_cost[i].val;
min_edge_idx = i;
}
}
choose[cnt] = low_cost[min_edge_idx];
visit[min_edge_idx] = 1;
low_cost[min_edge_idx] = {-1, -1, -1.0};
last_vis = min_edge_idx;
cnt++;
//特判
if(last_vis == hang_zhou_idx && visit[chang_sha_idx] == 0){
choose[cnt].from = hang_zhou_idx;
choose[cnt].to = chang_sha_idx;
choose[cnt].val = graph[hang_zhou_idx][chang_sha_idx];
visit[chang_sha_idx] = 1;
low_cost[chang_sha_idx] = {-1, -1, -1.0};
for(int i = 0; i < n; i++){
if(visit[i] == 0 && graph[last_vis][i] < low_cost[i].val){
low_cost[i].from = last_vis;
low_cost[i].to = i;
low_cost[i].val = graph[last_vis][i];
}
}
cnt++;
last_vis = chang_sha_idx;
}
else if(last_vis == chang_sha_idx && visit[hang_zhou_idx] == 0){
choose[cnt].from = chang_sha_idx;
choose[cnt].to = hang_zhou_idx;
choose[cnt].val = graph[chang_sha_idx][hang_zhou_idx];
visit[hang_zhou_idx] = 1;
low_cost[hang_zhou_idx] = {-1, -1, -1.0};
for(int i = 0; i < n; i++){
if(visit[i] == 0 && graph[last_vis][i] < low_cost[i].val){
low_cost[i].from = last_vis;
low_cost[i].to = i;
low_cost[i].val = graph[last_vis][i];
}
}
cnt++;
last_vis = hang_zhou_idx;
}
for(int i = 0; i < n; i++){
if(visit[i] == 0){
flag = 0;
break;
}
}
}
double sum = 0.0;
for(int i = 0; i < cnt; i++){
cout<<c[choose[i].from].name<<"<>"<<c[choose[i].to].name<<" "<<choose[i].val<<"KM"<<endl;
sum += choose[i].val;
}
/*
for(int i = 0; i < cnt; i++){
cout<<"('"<<c[choose[i].from].name<<"','"<<c[choose[i].to].name<<"',"<<choose[i].val<<"),"<<endl;
}
*/
cout<<"SUM LEN: "<<sum<<"km"<<endl;
return 0;
}
4
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstring>
#define R 6371.004 //平均半径
#define SUP 100000000
using namespace std;
struct city{
string name;
double longitude,latitude;
};
struct edge{
int from,to;
double val;
};
double rad(double angle){return angle * M_PI / 180;}
double earth_dist(city *pos_a, city *pos_b){
double long_a = rad(pos_a->longitude);double lat_a = rad(pos_a->latitude);
double long_b = rad(pos_b->longitude);double lat_b = rad(pos_b->latitude);
double c = sin(lat_a) * sin(lat_b) + cos(lat_a) * cos(lat_b) * cos(long_b - long_a);
return R * acos(c);
}
city c[50];
double graph[50][50] = {SUP};
int visit[50] = {0};
int n = 0;
edge choose[50], low_cost[50];
int main() {
int hong_kong_idx, macao_idx, guang_zhou_idx;
ifstream fin("data.txt");
while (!fin.eof()){
fin>>c[n].name>>c[n].longitude>>c[n].latitude;
if (c[n].name == "香港") hong_kong_idx = n;
else if (c[n].name == "澳门") macao_idx = n;
else if (c[n].name == "广州市") guang_zhou_idx = n;
n++;
}
fin.close();
//Build
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(i == j) graph[i][j] = 0;
else {
double dist = earth_dist(&c[i], &c[j]);
graph[i][j] = dist;graph[j][i] = dist;
}
}
}
int last_vis;
int cnt=0;int flag=0;
for(int i = 0; i < n; i++)low_cost[i] = {-1, -1, SUP};
visit[0] = 1;
last_vis = 0;
while (!flag){
flag = 1;
//Update
for(int i = 0; i < n; i++){
if(visit[i] == 0 && graph[last_vis][i] < low_cost[i].val){
bool spec_1, spec_2;
spec_1 = (last_vis == hong_kong_idx && i == macao_idx) || (last_vis == macao_idx && i == hong_kong_idx);
spec_2 = (last_vis == macao_idx && i == guang_zhou_idx) || (last_vis == guang_zhou_idx && i == macao_idx);
if (!spec_1 && !spec_2) {
low_cost[i].from = last_vis;
low_cost[i].to = i;
low_cost[i].val = graph[last_vis][i];
}
}
}
int min_edge_idx = -1;
double min_edge_dist = SUP;
//Search
for (int i = 0; i < n; i++) {
if(low_cost[i].val != -1.0 && low_cost[i].val < min_edge_dist){
min_edge_dist = low_cost[i].val;
min_edge_idx = i;
}
}
choose[cnt] = low_cost[min_edge_idx];
visit[min_edge_idx] = 1;
low_cost[min_edge_idx] = {-1, -1, -1.0};
last_vis = min_edge_idx;
cnt++;
for(int i = 0; i < n; i++){
if(visit[i] == 0){
flag = 0;
break;
}
}
}
double sum = 0.0;
for(int i = 0; i < cnt; i++){
cout<<c[choose[i].from].name<<"<>"<<c[choose[i].to].name<<" "<<choose[i].val<<"KM"<<endl;
sum += choose[i].val;
}
/*
for(int i = 0; i < cnt; i++){
cout<<"('"<<c[choose[i].from].name<<"','"<<c[choose[i].to].name<<"',"<<choose[i].val<<"),"<<endl;
}
*/
cout<<"SUM LEN: "<<sum<<"km"<<endl;
return 0;
}
5
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstring>
#include <map>
#define R 6371.004 //平均半径
#define SUP 100000000
using namespace std;
struct city{
string name;
double longitude,latitude;
};
struct edge{
int from,to;
double val;
};
double rad(double angle){return angle * M_PI / 180;}
double earth_dist(city *pos_a, city *pos_b){
double long_a = rad(pos_a->longitude);double lat_a = rad(pos_a->latitude);
double long_b = rad(pos_b->longitude);double lat_b = rad(pos_b->latitude);
double c = sin(lat_a) * sin(lat_b) + cos(lat_a) * cos(lat_b) * cos(long_b - long_a);
return R * acos(c);
}
city c[50];
double graph[50][50] = {SUP};
int visit[50] = {0};
int n = 0;
edge choose[50], low_cost[50];
int main() {
int north_tag;
string north_province[15] = {"济南市", "石家庄市", "天津市", "北京市", "沈阳市",
"长春市", "哈尔滨市", "郑州市", "太原市", "西安市",
"呼和浩特市", "兰州市", "银川市", "西宁市", "乌鲁木齐市"};
map<int, int> region_map;
ifstream fin("data.txt");
while (!fin.eof()){
fin>>c[n].name>>c[n].longitude>>c[n].latitude;
north_tag = 0;
for (int i = 0; i < 15; i++){
if (north_province[i] == c[n].name){
region_map[n] = 0;
north_tag = 1;
break;
}
}
if (north_tag == 0) region_map[n] = 1;
n++;
}
fin.close();
//Build
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(i == j) graph[i][j] = 0;
else {
double dist = earth_dist(&c[i], &c[j]);
graph[i][j] = dist;graph[j][i] = dist;
}
}
}
int last_vis;
int cnt=0;int flag=0;
//north
for(int i = 0; i < n; i++)low_cost[i] = {-1, -1, SUP};
visit[0] = 1; //沈阳
last_vis = 0;
while (!flag){
flag = 1;
//Update
for(int i = 0; i < n; i++){
if(region_map[i] == 0 && visit[i] == 0 && graph[last_vis][i] < low_cost[i].val){
low_cost[i].from = last_vis;
low_cost[i].to = i;
low_cost[i].val = graph[last_vis][i];
}
}
int min_edge_idx = -1;
double min_edge_dist = SUP;
//Search
for (int i = 0; i < n; i++) {
if(low_cost[i].val != -1.0 && low_cost[i].val < min_edge_dist){
min_edge_dist = low_cost[i].val;
min_edge_idx = i;
}
}
choose[cnt] = low_cost[min_edge_idx];
visit[min_edge_idx] = 1;
low_cost[min_edge_idx] = {-1, -1, -1.0};
last_vis = min_edge_idx;
cnt++;
for(int i = 0; i < n; i++){
if(region_map[i] == 0 && visit[i] == 0){
flag = 0;
break;
}
}
}
//south
for(int i = 0; i < n; i++)low_cost[i] = {-1, -1, SUP};
flag=0;
visit[15] = 1; //上海
last_vis = 15;
while (!flag){
flag = 1;
//Update
for(int i = 0; i < n; i++){
if(region_map[i] == 1 && visit[i] == 0 && graph[last_vis][i] < low_cost[i].val){
low_cost[i].from = last_vis;
low_cost[i].to = i;
low_cost[i].val = graph[last_vis][i];
}
}
int min_edge_idx = -1;
double min_edge_dist = SUP;
//Search
for (int i = 0; i < n; i++) {
if(low_cost[i].val != -1.0 && low_cost[i].val < min_edge_dist){
min_edge_dist = low_cost[i].val;
min_edge_idx = i;
}
}
choose[cnt] = low_cost[min_edge_idx];
visit[min_edge_idx] = 1;
low_cost[min_edge_idx] = {-1, -1, -1.0};
last_vis = min_edge_idx;
cnt++;
for(int i = 0; i < n; i++){
if(region_map[i] == 1 && visit[i] == 0){
flag = 0;
break;
}
}
}
int min_from, min_to;
double min_dist = SUP;
for (int i = 0; i < n; i++){
for(int j = 0; j < i; j++){
int spec = (region_map[i] == 0 && region_map[j] == 1) || (region_map[i] == 1 && region_map[j] == 0);
if (spec && graph[i][j] < min_dist){
min_from = i;
min_to = j;
min_dist = graph[i][j];
}
}
}
choose[cnt].from = min_from;
choose[cnt].to = min_to;
choose[cnt].val = min_dist;
cnt++;
double sum = 0.0;
for(int i = 0; i < cnt; i++){
cout<<c[choose[i].from].name<<"<>"<<c[choose[i].to].name<<" "<<choose[i].val<<"KM"<<endl;
sum += choose[i].val;
}
/*
for(int i = 0; i < cnt; i++){
cout<<"('"<<c[choose[i].from].name<<"','"<<c[choose[i].to].name<<"',"<<choose[i].val<<"),"<<endl;
}
*/
cout<<"SUM LEN: "<<sum<<"km"<<endl;
return 0;
}
data.txt
沈阳市 123.429092 41.796768
长春市 125.324501 43.886841
哈尔滨市 126.642464 45.756966
北京市 116.405289 39.904987
天津市 117.190186 39.125595
呼和浩特市 111.751990 40.841490
银川市 106.232480 38.486440
太原市 112.549248 37.857014
石家庄市 114.502464 38.045475
济南市 117.000923 36.675808
郑州市 113.665413 34.757977
西安市 108.948021 34.263161
武汉市 114.298569 30.584354
南京市 118.76741 32.041546
合肥市 117.283043 31.861191
上海市 121.472641 31.231707
长沙市 112.982277 28.19409
南昌市 115.892151 28.676493
杭州市 120.15358 30.287458
福州市 119.306236 26.075302
广州市 113.28064 23.125177
台北市 121.5200760 25.0307240
海口市 110.199890 20.044220
南宁市 108.320007 22.82402
重庆市 106.504959 29.533155
昆明市 102.71225 25.040609
贵阳市 106.713478 26.578342
成都市 104.065735 30.659462
兰州市 103.834170 36.061380
西宁市 101.777820 36.617290
拉萨市 91.11450 29.644150
乌鲁木齐市 87.616880 43.826630
香港 114.165460 22.275340
澳门 113.549130 22.198750
result.txt
题目1:
沈阳市<>长春市 279.076KM
长春市<>哈尔滨市 232.473KM
沈阳市<>天津市 605.429KM
天津市<>北京市 109.744KM
天津市<>石家庄市 262.662KM
石家庄市<>太原市 172.534KM
石家庄市<>济南市 268.228KM
太原市<>呼和浩特市 338.861KM
太原市<>郑州市 358.809KM
郑州市<>西安市 435.687KM
郑州市<>合肥市 465.513KM
合肥市<>南京市 141.475KM
南京市<>杭州市 235.447KM
杭州市<>上海市 164.04KM
合肥市<>武汉市 317.307KM
武汉市<>南昌市 262.154KM
南昌市<>长沙市 289.531KM
南昌市<>福州市 444.143KM
福州市<>台北市 250.622KM
西安市<>兰州市 505.96KM
兰州市<>西宁市 194.278KM
兰州市<>银川市 343.112KM
长沙市<>广州市 564.43KM
广州市<>澳门 106.634KM
澳门<>香港 64.0048KM
澳门<>海口市 421.967KM
海口市<>南宁市 365.228KM
南宁市<>贵阳市 447.881KM
贵阳市<>重庆市 329.197KM
重庆市<>成都市 265.982KM
贵阳市<>昆明市 435.472KM
成都市<>拉萨市 1249.67KM
西宁市<>乌鲁木齐市 1441.9KM
SUM LEN: 12369.5km
题目2:
西宁市<>郑州市 1092.57KM
西宁市<>兰州市 194.278KM
兰州市<>银川市 343.112KM
郑州市<>太原市 358.809KM
太原市<>石家庄市 172.534KM
石家庄市<>天津市 262.662KM
天津市<>北京市 109.744KM
石家庄市<>济南市 268.228KM
太原市<>呼和浩特市 338.861KM
郑州市<>西安市 435.687KM
郑州市<>合肥市 465.513KM
合肥市<>南京市 141.475KM
南京市<>杭州市 235.447KM
杭州市<>上海市 164.04KM
合肥市<>武汉市 317.307KM
武汉市<>南昌市 262.154KM
南昌市<>长沙市 289.531KM
南昌市<>福州市 444.143KM
福州市<>台北市 250.622KM
长沙市<>广州市 564.43KM
广州市<>澳门 106.634KM
澳门<>香港 64.0048KM
澳门<>海口市 421.967KM
海口市<>南宁市 365.228KM
南宁市<>贵阳市 447.881KM
贵阳市<>重庆市 329.197KM
重庆市<>成都市 265.982KM
贵阳市<>昆明市 435.472KM
天津市<>沈阳市 605.429KM
沈阳市<>长春市 279.076KM
长春市<>哈尔滨市 232.473KM
成都市<>拉萨市 1249.67KM
西宁市<>乌鲁木齐市 1441.9KM
SUM LEN: 12956.1km
题目3:
西宁市<>郑州市 1092.57KM
西宁市<>兰州市 194.278KM
兰州市<>银川市 343.112KM
郑州市<>太原市 358.809KM
太原市<>石家庄市 172.534KM
石家庄市<>天津市 262.662KM
天津市<>北京市 109.744KM
石家庄市<>济南市 268.228KM
太原市<>呼和浩特市 338.861KM
郑州市<>西安市 435.687KM
郑州市<>合肥市 465.513KM
合肥市<>南京市 141.475KM
南京市<>杭州市 235.447KM
杭州市<>长沙市 733.531KM
杭州市<>上海市 164.04KM
长沙市<>南昌市 289.531KM
南昌市<>武汉市 262.154KM
南昌市<>福州市 444.143KM
福州市<>台北市 250.622KM
长沙市<>广州市 564.43KM
广州市<>澳门 106.634KM
澳门<>香港 64.0048KM
澳门<>海口市 421.967KM
海口市<>南宁市 365.228KM
南宁市<>贵阳市 447.881KM
贵阳市<>重庆市 329.197KM
重庆市<>成都市 265.982KM
贵阳市<>昆明市 435.472KM
天津市<>沈阳市 605.429KM
沈阳市<>长春市 279.076KM
长春市<>哈尔滨市 232.473KM
成都市<>拉萨市 1249.67KM
西宁市<>乌鲁木齐市 1441.9KM
SUM LEN: 13372.3km
题目4:
沈阳市<>长春市 279.076KM
长春市<>哈尔滨市 232.473KM
沈阳市<>天津市 605.429KM
天津市<>北京市 109.744KM
天津市<>石家庄市 262.662KM
石家庄市<>太原市 172.534KM
石家庄市<>济南市 268.228KM
太原市<>呼和浩特市 338.861KM
太原市<>郑州市 358.809KM
郑州市<>西安市 435.687KM
郑州市<>合肥市 465.513KM
合肥市<>南京市 141.475KM
南京市<>杭州市 235.447KM
杭州市<>上海市 164.04KM
合肥市<>武汉市 317.307KM
武汉市<>南昌市 262.154KM
南昌市<>长沙市 289.531KM
南昌市<>福州市 444.143KM
福州市<>台北市 250.622KM
西安市<>兰州市 505.96KM
兰州市<>西宁市 194.278KM
兰州市<>银川市 343.112KM
长沙市<>广州市 564.43KM
广州市<>香港 131.027KM
广州市<>海口市 467.756KM
海口市<>南宁市 365.228KM
海口市<>澳门 421.967KM
南宁市<>贵阳市 447.881KM
贵阳市<>重庆市 329.197KM
重庆市<>成都市 265.982KM
贵阳市<>昆明市 435.472KM
成都市<>拉萨市 1249.67KM
西宁市<>乌鲁木齐市 1441.9KM
SUM LEN: 12797.6km
题目5:
沈阳市<>长春市 279.076KM
长春市<>哈尔滨市 232.473KM
沈阳市<>天津市 605.429KM
天津市<>北京市 109.744KM
天津市<>石家庄市 262.662KM
石家庄市<>太原市 172.534KM
石家庄市<>济南市 268.228KM
太原市<>呼和浩特市 338.861KM
太原市<>郑州市 358.809KM
郑州市<>西安市 435.687KM
西安市<>兰州市 505.96KM
兰州市<>西宁市 194.278KM
兰州市<>银川市 343.112KM
西宁市<>乌鲁木齐市 1441.9KM
上海市<>杭州市 164.04KM
杭州市<>南京市 235.447KM
南京市<>合肥市 141.475KM
合肥市<>武汉市 317.307KM
武汉市<>南昌市 262.154KM
南昌市<>长沙市 289.531KM
南昌市<>福州市 444.143KM
福州市<>台北市 250.622KM
长沙市<>广州市 564.43KM
广州市<>澳门 106.634KM
澳门<>香港 64.0048KM
澳门<>海口市 421.967KM
海口市<>南宁市 365.228KM
南宁市<>贵阳市 447.881KM
贵阳市<>重庆市 329.197KM
重庆市<>成都市 265.982KM
贵阳市<>昆明市 435.472KM
成都市<>拉萨市 1249.67KM
合肥市<>郑州市 465.513KM
SUM LEN: 12369.5km
debug.cpp
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 1000000
struct Edge{
int from,to;
double val;
}edge[MAXN];
int m,n;
int father[MAXN];
bool cmp(Edge x,Edge y){
return x.val<y.val;
}
int find(int x){
//有路径压缩的查询
if(father[x]!=x)father[x]=find(father[x]);
return father[x];
}
int main(){
cin>>n>>m;
for(int i=0;i<m;i++)cin>>(edge[i].from)>>(edge[i].to)>>(edge[i].val);
//kruskal
double ans=0.0f;
int cnt=0;
for(int i=1;i<=n;i++)father[i]=i;
sort(edge,edge+m,cmp);
int x,y;
for(int i=0;i<m;i++){
x=edge[i].from;y=edge[i].to;
if(find(x)!=find(y)){
father[find(x)]=find(y);
ans+=edge[i].val;
++cnt;
if(cnt==n-1)break;
}
}
if(cnt==n-1)cout<<ans;
return 0;
}
debug1.cpp
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#define R register int
using namespace std;
int k,n,m,cnt,sum,ai,bi,ci,head[5005],dis[5005],vis[5005];
struct Edge
{
int v,w,next;
}e[400005];
void add(int u,int v,int w)
{
e[++k].v=v;
e[k].w=w;
e[k].next=head[u];
head[u]=k;
}
typedef pair <int,int> pii;
priority_queue <pii,vector<pii>,greater<pii> > q;
void prim()
{
dis[1]=0;
q.push(make_pair(0,1));
while(!q.empty()&&cnt<n)
{
int d=q.top().first,u=q.top().second;
q.pop();
if(vis[u]) continue;
cnt++;
sum+=d;
vis[u]=1;
for(R i=head[u];i!=-1;i=e[i].next)
if(e[i].w<dis[e[i].v])
dis[e[i].v]=e[i].w,q.push(make_pair(dis[e[i].v],e[i].v));
}
}
int main()
{
memset(dis,127,sizeof(dis));
memset(head,-1,sizeof(head));
scanf("%d%d",&n,&m);
for(R i=1;i<=m;i++)
{
scanf("%d%d%d",&ai,&bi,&ci);
add(ai,bi,ci);
add(bi,ai,ci);
}
prim();
if (cnt==n)printf("%d",sum);
else printf("orz");
}
oj
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 1000000
struct Edge{
int from,to,val;
}edge[MAXN];
int m,n;
int father[MAXN];
bool cmp(Edge x,Edge y){
return x.val<y.val;
}
int find(int x){
//有路径压缩的查询
if(father[x]!=x)father[x]=find(father[x]);
return father[x];
}
int main(){
cin>>n>>m;
for(int i=0;i<m;i++)cin>>(edge[i].from)>>(edge[i].to)>>(edge[i].val);
//kruskal
int ans=0,cnt=0;
for(int i=1;i<=n;i++)father[i]=i;
sort(edge,edge+m,cmp);
int x,y;
for(int i=0;i<m;i++){
x=edge[i].from;y=edge[i].to;
if(find(x)!=find(y)){
father[find(x)]=find(y);
ans+=edge[i].val;
++cnt;
if(cnt==n-1)break;
}
}
if(cnt==n-1)cout<<ans;
return 0;
}