核心代码
1
#include <iostream>
#include <fstream>
#include <stack>
#include <cstring>
#include <map>
#include <ctime>
#define INF 100000005
using namespace std;
int graph[50][50], d[50], visit[50] = {0}, pre[50] = {0};
void find_path(int from, int to, int n){
int flag = 0;
for(int i = 0; i < n; i++) d[i] = INF;
for(int i = 0; i < n; i++) visit[i] = 0;
d[from] = 0;
while (!flag){
int min_dist = INF, min_idx = -1;
for(int i = 0; i < n; i++){
if (visit[i] == 0 && d[i] < min_dist){
min_dist = d[i];
min_idx = i;
}
}
visit[min_idx] = 1;
if(min_idx == to) break;
for(int i = 0; i < n; i++){
if (visit[i] == 0 && graph[min_idx][i] != INF){
if(d[i] > d[min_idx] + graph[min_idx][i]) {
d[i] = d[min_idx] + graph[min_idx][i];
pre[i] = min_idx;
}
}
}
flag = 1;
for (int i = 0; i < n; i++) {
if (visit[i] == 0){
flag = 0;
break;
}
}
}
}
int main() {
double startTime,endTime;
ifstream fin("data.txt");
stack<int> path;
map<string, int> location_index;
map<int, string> inv_location_index;
int n = 0, start, end, flag = 0;
string start_city, end_city;
for(int i = 0; i < 50; i++){
for(int j = 0; j < 50; j++) {
graph[i][j] = INF;graph[j][i] = INF;
}
}
while(!fin.eof()){
string from, to;
int from_index, to_index, distance, speed;
fin>>from>>to>>distance>>speed;
if (location_index.find(from) == location_index.end()){
from_index = n;
location_index[from] = from_index;
inv_location_index[from_index] = from;
n++;
}
else from_index = location_index[from];
if (location_index.find(to) == location_index.end()){
to_index = n;
location_index[to] = to_index;
inv_location_index[to_index] = to;
n++;
}
else to_index = location_index[to];
graph[from_index][to_index] = distance;graph[to_index][from_index] = distance;
}
fin.close();
start_city = "成都";end_city = "江达";
start = location_index[start_city];
end = location_index[end_city];
//startTime=clock();
find_path(start, end, n);
//endTime=clock();
//cout<<"It takes "<<1000000*(endTime-startTime) / CLOCKS_PER_SEC<<"微秒"<<endl;
//recall
int cur = end;
path.push(end);
while(cur != start){
path.push(pre[cur]);
cur = pre[cur];
}
cout<<"Path:";
while(!path.empty()) {
cout << inv_location_index[path.top()] ;
path.pop();
if(!path.empty())cout<<">";
}
cout<<endl;
cout<<"Total: "<<d[end]<<"km"<<endl;
return 0;
}
2
#include <iostream>
#include <fstream>
#include <stack>
#include <cstring>
#include <map>
#define INF 100000005
using namespace std;
int graph[50][50], d[50], visit[50] = {0}, pre[50] = {0};
void find_path(int from, int to, int n){
int flag = 0;
for(int i = 0; i < n; i++) d[i] = INF;
for(int i = 0; i < n; i++) visit[i] = 0;
d[from] = 0;
while (!flag){
int min_dist = INF, min_idx = -1;
for(int i = 0; i < n; i++){
if (visit[i] == 0 && d[i] < min_dist){
min_dist = d[i];
min_idx = i;
}
}
visit[min_idx] = 1;
if(min_idx == to) break;
for(int i = 0; i < n; i++){
if (visit[i] == 0 && graph[min_idx][i] != INF){
if(d[i] > d[min_idx] + graph[min_idx][i]) {
d[i] = d[min_idx] + graph[min_idx][i];
pre[i] = min_idx;
}
}
}
flag = 1;
for (int i = 0; i < n; i++) {
if (visit[i] == 0){
flag = 0;
break;
}
}
}
}
int main() {
ifstream fin("data.txt");
stack<int> path;
int tot_dist = 0;
map<string, int> location_index;
map<int, string> inv_location_index;
int n = 0, start, mid, end;
string start_city, mid_city, end_city;
for(int i = 0; i < 50; i++){
for(int j = 0; j < 50; j++) {
graph[i][j] = INF;
graph[j][i] = INF;
}
}
while(!fin.eof()){
string from, to;
int from_index, to_index, distance, speed;
fin>>from>>to>>distance>>speed;
if (location_index.find(from) == location_index.end()){
from_index = n;
location_index[from] = from_index;
inv_location_index[from_index] = from;
n++;
}
else{
from_index = location_index[from];
}
if (location_index.find(to) == location_index.end()){
to_index = n;
location_index[to] = to_index;
inv_location_index[to_index] = to;
n++;
}
else{
to_index = location_index[to];
}
graph[from_index][to_index] = distance;
graph[to_index][from_index] = distance;
}
start_city = "成都";
mid_city = "理塘";
end_city = "江达";
start = location_index[start_city];
mid = location_index[mid_city];
end = location_index[end_city];
find_path(mid, end, n);
int cur = end;
path.push(end);
while(cur != mid){
path.push(pre[cur]);
cur = pre[cur];
}
tot_dist += d[end];
find_path(start, mid, n);
cur = pre[mid];
path.push(pre[mid]);
while(cur != start){
path.push(pre[cur]);
cur = pre[cur];
}
cout<<"Path:";
while(!path.empty()){
cout<<inv_location_index[path.top()];
path.pop();
if(!path.empty())cout<<">";
}
tot_dist += d[mid];
cout<<endl;
cout<<"Total: "<<tot_dist<<"km"<<endl;
fin.close();
return 0;
}
3
#include <iostream>
#include <fstream>
#include <stack>
#include <cstring>
#include <map>
#define INF 100000005
using namespace std;
int graph[50][50], d[50], visit[50] = {0}, pre[50] = {0};
void find_path(int from, int to, int n){
int flag = 0;
for(int i = 0; i < n; i++) d[i] = INF;
for(int i = 0; i < n; i++) visit[i] = 0;
d[from] = 0;
while (!flag){
int min_dist = INF, min_idx = -1;
for(int i = 0; i < n; i++){
if (visit[i] == 0 && d[i] < min_dist){
min_dist = d[i];
min_idx = i;
}
}
visit[min_idx] = 1;
if(min_idx == to) break;
for(int i = 0; i < n; i++){
if (visit[i] == 0 && graph[min_idx][i] != INF){
if(d[i] > d[min_idx] + graph[min_idx][i]) {
d[i] = d[min_idx] + graph[min_idx][i];
pre[i] = min_idx;
}
}
}
flag = 1;
for (int i = 0; i < n; i++) {
if (visit[i] == 0){
flag = 0;
break;
}
}
}
}
int main() {
ifstream fin("data.txt");
stack<int> path_1, path_2;
int tot_dist_1 = 0, tot_dist_2 = 0;
map<string, int> location_index;
map<int, string> inv_location_index;
int n = 0, start, mid_1, mid_2, end;
string start_city, mid_city_1, mid_city_2, end_city;
for(int i = 0; i < 50; i++){
for(int j = 0; j < 50; j++) {
graph[i][j] = INF;
graph[j][i] = INF;
}
}
while(!fin.eof()){
string from, to;
int from_index, to_index, distance, speed;
fin>>from>>to>>distance>>speed;
if (location_index.find(from) == location_index.end()){
from_index = n;
location_index[from] = from_index;
inv_location_index[from_index] = from;
n++;
}
else{
from_index = location_index[from];
}
if (location_index.find(to) == location_index.end()){
to_index = n;
location_index[to] = to_index;
inv_location_index[to_index] = to;
n++;
}
else{
to_index = location_index[to];
}
graph[from_index][to_index] = distance;
graph[to_index][from_index] = distance;
}
start_city = "成都";
mid_city_1 = "理塘";
mid_city_2 = "道孚";
end_city = "江达";
start = location_index[start_city];
mid_1 = location_index[mid_city_1];
mid_2 = location_index[mid_city_2];
end = location_index[end_city];
//Find path 1
find_path(mid_1, end, n);
int cur = end;
path_1.push(end);
while(cur != mid_1){
path_1.push(pre[cur]);
cur = pre[cur];
}
tot_dist_1 += d[end];
find_path(start, mid_1, n);
cur = pre[mid_1];
path_1.push(pre[mid_1]);
while(cur != start){
path_1.push(pre[cur]);
cur = pre[cur];
}
tot_dist_1 += d[mid_1];
//Find path 2
find_path(mid_2, end, n);
cur = end;
path_2.push(end);
while(cur != mid_2){
path_2.push(pre[cur]);
cur = pre[cur];
}
tot_dist_2 += d[end];
find_path(start, mid_2, n);
cur = pre[mid_2];
path_2.push(pre[mid_2]);
while(cur != start){
path_2.push(pre[cur]);
cur = pre[cur];
}
tot_dist_2 += d[mid_2];
if(tot_dist_1 <= tot_dist_2){
cout<<"途径 理塘"<<endl;
cout<<"Path:";
while(!path_1.empty()){
int p = path_1.top();
cout<<inv_location_index[p];
path_1.pop();
if(!path_1.empty())cout<<">";
}
cout<<endl;
cout<<"Total: "<<tot_dist_1<<"km"<<endl;
}
else{
cout<<"途径 道孚"<<endl;
cout<<"Path:";
while(!path_2.empty()){
int p = path_2.top();
cout<<inv_location_index[p];
path_2.pop();
if(!path_2.empty())cout<<">";
}
cout<<endl;
cout<<"Total: "<<tot_dist_2<<"km"<<endl;
}
fin.close();
return 0;
}
4_2
#include <iostream>
#include <fstream>
#include <stack>
#include <cstring>
#include <map>
#define INF 100000005
using namespace std;
int graph_dist[50][50], visit[50] = {0}, pre[50] = {0};
double graph[50][50],d[50];
void find_path(int from, int to, int n){
int flag = 0;
for(int i = 0; i < n; i++) d[i] = INF;
for(int i = 0; i < n; i++) visit[i] = 0;
d[from] = 0;
while (!flag){
double min_dist = INF;
int min_idx = -1;
for(int i = 0; i < n; i++){
if (visit[i] == 0 && d[i] < min_dist){
min_dist = d[i];
min_idx = i;
}
}
visit[min_idx] = 1;
if(min_idx == to) break;
for(int i = 0; i < n; i++){
if (visit[i] == 0 && graph[min_idx][i] != INF){
if(d[i] > d[min_idx] + graph[min_idx][i]) {
d[i] = d[min_idx] + graph[min_idx][i];
pre[i] = min_idx;
}
}
}
flag = 1;
for (int i = 0; i < n; i++) {
if (visit[i] == 0){
flag = 0;
break;
}
}
}
}
int main() {
ifstream fin("data.txt");
stack<int> path;
double tot_time = 0.0;
int tot_dist = 0;
map<string, int> location_index;
map<int, string> inv_location_index;
int n = 0, start, mid, end;
string start_city, mid_city, end_city;
for(int i = 0; i < 50; i++){
for(int j = 0; j < 50; j++) {
graph[i][j] = INF;
graph[j][i] = INF;
graph_dist[i][j] = INF;
graph_dist[j][i] = INF;
}
}
while(!fin.eof()){
string from, to;
int from_index, to_index, distance, speed;
fin>>from>>to>>distance>>speed;
if (location_index.find(from) == location_index.end()){
from_index = n;
location_index[from] = from_index;
inv_location_index[from_index] = from;
n++;
}
else{
from_index = location_index[from];
}
if (location_index.find(to) == location_index.end()){
to_index = n;
location_index[to] = to_index;
inv_location_index[to_index] = to;
n++;
}
else{
to_index = location_index[to];
}
graph[from_index][to_index] = (double)distance / speed;
graph[to_index][from_index] = (double)distance / speed;
graph_dist[from_index][to_index] = distance;
graph_dist[to_index][from_index] = distance;
}
start_city = "成都";
mid_city = "理塘";
end_city = "江达";
start = location_index[start_city];
mid = location_index[mid_city];
end = location_index[end_city];
find_path(mid, end, n);
int cur = end;
path.push(end);
while(cur != mid){
path.push(pre[cur]);
tot_dist += graph_dist[cur][pre[cur]];
cur = pre[cur];
}
tot_time += d[end];
find_path(start, mid, n);
cur = pre[mid];
path.push(pre[mid]);
while(cur != start){
path.push(pre[cur]);
tot_dist += graph_dist[cur][pre[cur]];
cur = pre[cur];
}
cout<<"Path:";
while(!path.empty()){
cout<<inv_location_index[path.top()];
path.pop();
if(!path.empty())cout<<">";
}
tot_time += d[mid];
cout<<endl;
tot_dist += graph_dist[mid][pre[mid]];
cout<<"Total Time: "<<tot_time<<"h"<<endl;
cout<<"Total Dist: "<<tot_dist<<"km"<<endl;
fin.close();
return 0;
}
4_3
#include <iostream>
#include <fstream>
#include <stack>
#include <cstring>
#include <map>
#define INF 100000005
using namespace std;
int graph_dist[50][50], visit[50] = {0}, pre[50] = {0};
double graph[50][50],d[50];
void find_path(int from, int to, int n){
int flag = 0;
for(int i = 0; i < n; i++) d[i] = INF;
for(int i = 0; i < n; i++) visit[i] = 0;
d[from] = 0;
while (!flag){
double min_dist = INF;
int min_idx = -1;
for(int i = 0; i < n; i++){
if (visit[i] == 0 && d[i] < min_dist){
min_dist = d[i];
min_idx = i;
}
}
visit[min_idx] = 1;
if(min_idx == to) break;
for(int i = 0; i < n; i++){
if (visit[i] == 0 && graph[min_idx][i] != INF){
if(d[i] > d[min_idx] + graph[min_idx][i]) {
d[i] = d[min_idx] + graph[min_idx][i];
pre[i] = min_idx;
}
}
}
flag = 1;
for (int i = 0; i < n; i++) {
if (visit[i] == 0){
flag = 0;
break;
}
}
}
}
int main() {
ifstream fin("data.txt");
stack<int> path_1, path_2;
double tot_time_1 = 0.0, tot_time_2 = 0.0;
int tot_dist_1 = 0, tot_dist_2 = 0;
map<string, int> location_index;
map<int, string> inv_location_index;
int n = 0, start, mid_1, mid_2, end;
string start_city, mid_city_1, mid_city_2, end_city;
for(int i = 0; i < 50; i++){
for(int j = 0; j < 50; j++) {
graph[i][j] = INF;
graph[j][i] = INF;
graph_dist[i][j] = INF;
graph_dist[j][i] = INF;
}
}
while(!fin.eof()){
string from, to;
int from_index, to_index, distance, speed;
fin>>from>>to>>distance>>speed;
if (location_index.find(from) == location_index.end()){
from_index = n;
location_index[from] = from_index;
inv_location_index[from_index] = from;
n++;
}
else{
from_index = location_index[from];
}
if (location_index.find(to) == location_index.end()){
to_index = n;
location_index[to] = to_index;
inv_location_index[to_index] = to;
n++;
}
else{
to_index = location_index[to];
}
graph[from_index][to_index] = (double)distance / speed;
graph[to_index][from_index] = (double)distance / speed;
graph_dist[from_index][to_index] = distance;
graph_dist[to_index][from_index] = distance;
}
start_city = "成都";
mid_city_1 = "理塘";
mid_city_2 = "道孚";
end_city = "江达";
start = location_index[start_city];
mid_1 = location_index[mid_city_1];
mid_2 = location_index[mid_city_2];
end = location_index[end_city];
//Find path 1
find_path(mid_1, end, n);
int cur = end;
path_1.push(end);
while(cur != mid_1){
path_1.push(pre[cur]);
tot_dist_1 += graph_dist[cur][pre[cur]];
cur = pre[cur];
}
tot_time_1 += d[end];
find_path(start, mid_1, n);
cur = pre[mid_1];
path_1.push(pre[mid_1]);
while(cur != start){
path_1.push(pre[cur]);
tot_dist_1 += graph_dist[cur][pre[cur]];
cur = pre[cur];
}
tot_dist_1 += graph_dist[mid_1][pre[mid_1]];
tot_time_1 += d[mid_1];
//Find path 2
find_path(mid_2, end, n);
cur = end;
path_2.push(end);
while(cur != mid_2){
path_2.push(pre[cur]);
tot_dist_2 += graph_dist[cur][pre[cur]];
cur = pre[cur];
}
tot_time_2 += d[end];
find_path(start, mid_2, n);
cur = pre[mid_2];
path_2.push(pre[mid_2]);
while(cur != start){
path_2.push(pre[cur]);
tot_dist_2 += graph_dist[cur][pre[cur]];
cur = pre[cur];
}
tot_dist_2 += graph_dist[mid_2][pre[mid_2]];
tot_time_2 += d[mid_2];
if(tot_time_1 <= tot_time_2){
cout<<"途径 理塘"<<endl;
cout<<"Path:";
while(!path_1.empty()){
int p = path_1.top();
cout<<inv_location_index[p];
path_1.pop();
if(!path_1.empty())cout<<">";
}
cout<<endl;
cout<<"Total Time: "<<tot_time_1<<"h"<<endl;
cout<<"Total Dist: "<<tot_dist_1<<"km"<<endl;
}
else{
cout<<"途径 道孚"<<endl;
cout<<"Path:";
while(!path_2.empty()){
int p = path_2.top();
cout<<inv_location_index[p];
path_2.pop();
if(!path_2.empty())cout<<">";
}
cout<<endl;
cout<<"Total Time: "<<tot_time_2<<"h"<<endl;
cout<<"Total Dist: "<<tot_dist_2<<"km"<<endl;
}
fin.close();
return 0;
}
5
#include <iostream>
#include <fstream>
#include <stack>
#include <cstring>
#include <map>
#include <ctime>
#define INF 100000005
using namespace std;
int graph[50][50], d1[50], d2[50], visit_1[50], visit_2[50], pred_1[50] = {0}, pred_2[50] = {0}, inter_idx;
void find_path(int from, int to, int n){
int flag = 0;
for(int i = 0; i < n; i++) d1[i] = INF;
for(int i = 0; i < n; i++) d2[i] = INF;
for(int i = 0; i < n; i++) visit_1[i] = 0;
for(int i = 0; i < n; i++) visit_2[i] = 0;
d1[from] = 0;
d2[to] = 0;
while (!flag){
int min_dist_1 = INF, min_dist_2 = INF, min_idx_1 = -1, min_idx_2 = -1;
for(int i = 0; i < n; i++){
if (visit_1[i] == 0 && d1[i] < min_dist_1){
min_dist_1 = d1[i];
min_idx_1 = i;
}
}
visit_1[min_idx_1] = 1;
for(int i = 0; i < n; i++){
if (visit_2[i] == 0 && d2[i] < min_dist_2){
min_dist_2 = d2[i];
min_idx_2 = i;
}
}
visit_2[min_idx_2] = 1;
if(visit_1[min_idx_2] == 1 || visit_2[min_idx_1] == 1) {
inter_idx = visit_1[min_idx_2] ? min_idx_2 : min_idx_1;
break;
}
if(min_idx_1 == to || min_idx_2 == from) break;
for(int i = 0; i < n; i++){
if (visit_1[i] == 0 && graph[min_idx_1][i] != INF){
if(d1[i] > d1[min_idx_1] + graph[min_idx_1][i]) {
d1[i] = d1[min_idx_1] + graph[min_idx_1][i];
pred_1[i] = min_idx_1;
}
}
}
for(int i = 0; i < n; i++){
if (visit_2[i] == 0 && graph[min_idx_2][i] != INF){
if(d2[i] > d2[min_idx_2] + graph[min_idx_2][i]) {
d2[i] = d2[min_idx_2] + graph[min_idx_2][i];
pred_2[i] = min_idx_2;
}
}
}
flag = 1;
for (int i = 0; i < n; i++) {
if (visit_1[i] == 0 || visit_2[i] == 0){
flag = 0;
break;
}
}
}
}
int main() {
double startTime,endTime;
ifstream fin("data.txt");
stack<int> path;
map<string, int> location_index;
map<int, string> inv_location_index;
int n = 0, start, end, flag = 0, tot_dist = 0;
string start_city, end_city;
for(int i = 0; i < 50; i++){
for(int j = 0; j < 50; j++) {
graph[i][j] = INF;
graph[j][i] = INF;
}
}
while(!fin.eof()){
string from, to;
int from_index, to_index, distance, speed;
fin>>from>>to>>distance>>speed;
if (location_index.find(from) == location_index.end()){
from_index = n;
location_index[from] = from_index;
inv_location_index[from_index] = from;
n++;
}
else{
from_index = location_index[from];
}
if (location_index.find(to) == location_index.end()){
to_index = n;
location_index[to] = to_index;
inv_location_index[to_index] = to;
n++;
}
else{
to_index = location_index[to];
}
graph[from_index][to_index] = distance;
graph[to_index][from_index] = distance;
}
start_city = "成都";
end_city = "江达";
start = location_index[start_city];
end = location_index[end_city];
//startTime=clock();
find_path(start, end, n);
//endTime=clock();
//cout<<"It takes "<<1000000*(endTime-startTime) / CLOCKS_PER_SEC<<"微秒"<<endl;
int cur = inter_idx;
path.push(inter_idx);
while(cur != start){
path.push(pred_1[cur]);
cur = pred_1[cur];
}
tot_dist += d1[inter_idx];
cout<<"Path:";
while(!path.empty()) {
cout << inv_location_index[path.top()];
if(!path.empty())cout<<">";
path.pop();
}
cur = inter_idx;
while(cur != end){
cout<<inv_location_index[pred_2[cur]];
if(pred_2[cur]!=end)cout<<">";
cur = pred_2[cur];
}
tot_dist += d2[inter_idx];
cout<<endl;
cout<<"Total: "<<tot_dist<<"km"<<endl;
fin.close();
return 0;
}
data.txt
成都 雅安 140 80
雅安 天全 28 60
天全 泸定 168 60
泸定 泸定和康定的中间点 24 60
泸定和康定的中间点 康定 25 60
康定 新都桥 75 60
新都桥 雅江 71 60
雅江 理塘 135 60
理塘 巴塘 180 60
巴塘 白玉 195 40
理塘 新龙 153 40
雅江 道孚 183 40
新都桥 塔公 35 60
塔公 八美 28 60
泸定和康定的中间点 丹巴 112 60
白玉 德格 99 40
新龙 甘孜 107 40
道孚 炉霍 78 60
炉霍 甘孜 97 60
炉霍 翁达 71 60
八美 道孚 83 60
八美 丹巴 83 60
丹巴 小金 58 60
丹巴 金川 92 60
小金 日隆 52 60
日隆 映秀 140 60
映秀 都江堰 42 60
都江堰 成都 50 60
映秀 汶川 57 60
汶川 理县 57 60
理县 马尔康 144 60
马尔康 翁达和马尔康之间靠近马尔康的分界点 48 60
翁达和马尔康之间靠近马尔康的分界点 金川 58 60
翁达和马尔康之间靠近马尔康的分界点 翁达和马尔康之间靠近翁达的分界点 196 60
翁达和马尔康之间靠近翁达的分界点 翁达 38 60
翁达和马尔康之间靠近翁达的分界点 壤塘 41 60
翁达 色达 83 60
色达 甘孜 158 40
甘孜 马尼干戈 95 60
马尼干戈 新路海 9 60
新路海 德格 115 60
德格 江达 18 60
白玉 甘孜 242 40