#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_map>
#include <vector>
using namespace std;
const int N = 100;
unordered_map<string, int> umap_ci; //城市_数字的映射
unordered_map<int, string> umap_ic; //数字_城市
int g[N][N];
int st[N], dist[N], pre[N], del[N];
int n = 19, idx = 20;
void init()
{
memset(g, 0x3f, sizeof g);
umap_ci["北京"] = 1;
umap_ci["天津"] = 2;
umap_ci["郑州"] = 3;
umap_ci["徐州"] = 4;
umap_ci["上海"] = 5;
umap_ci["武汉"] = 6;
umap_ci["南昌"] = 7;
umap_ci["株洲"] = 8;
umap_ci["福州"] = 9;
umap_ci["广州"] = 10;
umap_ci["深圳"] = 11;
umap_ci["西宁"] = 12;
umap_ci["柳州"] = 13;
umap_ci["贵阳"] = 14;
umap_ci["昆明"] = 15;
umap_ci["成都"] = 16;
umap_ci["西安"] = 17;
umap_ci["兰州"] = 18;
umap_ci["南宁"] = 19;
umap_ic[1] = "北京";
umap_ic[2] = "天津";
umap_ic[3] = "郑州";
umap_ic[4] = "徐州";
umap_ic[5] = "上海";
umap_ic[6] = "武汉";
umap_ic[7] = "南昌";
umap_ic[8] = "株洲";
umap_ic[9] = "福州";
umap_ic[10] = "广州";
umap_ic[11] = "深圳";
umap_ic[12] = "西宁";
umap_ic[13] = "柳州";
umap_ic[14] = "贵阳";
umap_ic[15] = "昆明";
umap_ic[16] = "成都";
umap_ic[17] = "西安";
umap_ic[18] = "兰州";
umap_ic[19] = "南宁";
//建立无向边
g[1][2] = g[2][1] = 137;
g[1][3] = g[3][1] = 695;
g[2][4] = g[4][2] = 674;
g[3][4] = g[4][3] = 349;
g[3][6] = g[6][3] = 534;
g[3][17] = g[17][3] = 511;
g[4][5] = g[5][4] = 651;
g[5][7] = g[7][5] = 825;
g[6][8] = g[8][6] = 409;
g[7][8] = g[8][7] = 367;
g[7][9] = g[9][7] = 622;
g[8][10] = g[10][8] = 675;
g[8][13] = g[13][8] = 672;
g[8][14] = g[14][8] = 902;
g[10][11] = g[11][10] = 140;
g[19][13] = g[13][19] = 255;
g[13][14] = g[14][13] = 607;
g[14][16] = g[16][14] = 967;
g[14][15] = g[15][14] = 639;
g[15][16] = g[16][15] = 1100;
g[16][17] = g[17][16] = 842;
g[17][18] = g[18][17] = 676;
g[18][12] = g[12][18] = 216;
}
int dijkstra(int startId, int endId)
{
memset(dist, 0x3f, sizeof dist);
memset(st, 0, sizeof st);
memset(pre, 0, sizeof pre);
dist[startId] = 0;
for (int i = 0; i < n; i++)
{
int t = -1;
for (int j = 1; j <= n; j++)
{
if (!st[j] && !del[j] && (dist[t] > dist[j] || t == -1))
t = j;
}
st[t] = 1;
if (t == endId) break;
for (int k = 1; k <= n; k++)
{
if (dist[k] > dist[t] + g[t][k])
{
dist[k] = dist[t] + g[t][k];
pre[k] = t;
}
}
}
if (dist[endId] == 0x3f3f3f3f) return -1;
else return dist[endId];
}
bool add(string a)
{
if (idx > 100) return 0;
umap_ci[a] = idx; umap_ic[idx] = a;
string city; int w;
cout << "请输入相连的城市及其距离: " << endl;
while (cin >> city >> w)
{
if (city == "0" && w == 0) break; //输入错误数据会结束
int id = umap_ci[city];
g[id][idx] = g[idx][id] = w;
}
idx++; n++;
return 1;
}
bool delCity(string a)
{
if (umap_ci.find(a) == umap_ci.end()) return 0;
int id = umap_ci[a];
del[id] = 1;
for (int i = 1; i <= n; i++)
g[id][i] = g[i][id] = 0x3f3f3f3f;
return 1;
}
void findAdjacencyPoint(string city)
{
int id = umap_ci[city];
cout << "临界点：";
for (int i = 1; i <= n; i++)
{
if (g[id][i] < 0x3f3f3f3f)
cout << umap_ic[i] << " ";
}
cout << endl;
}
bool modify(string start, string end, int w)
{
int startId = umap_ci[start];
int endId = umap_ci[end];
if (del[startId] || del[endId] || umap_ci.find(start) == umap_ci.end() || umap_ci.find(end) == umap_ci.end())
{
cout << "起点或者终点城市没有添加过或者已经被删除" << endl;
return false;
}
if (w <= 0 || w >= 0x3f3f3f3f)
{
cout << "输入的距离不是一个合理的值！！！" << endl;
return false;
}
g[startId][endId] = g[endId][startId] = w;
return true;
}
void findShortestPath()
{
string start, end;
vector<string> v; //存储路径的向量
cout << "请输入起始地和目标地点: " << endl;
cin >> start >> end;
int startId = umap_ci[start];
int endId = umap_ci[end];
if (del[startId] || del[endId] || umap_ci.find(start) == umap_ci.end() || umap_ci.find(end) == umap_ci.end())
{
cout << "起点或者终点城市没有添加过或者已经被删除" << endl;
return;
}
int t = dijkstra(startId, endId);
if (t == -1)
{
cout << "城市" << " " << start << " " << "到不了城市 " << end << " " << endl;
return;
}
while (endId)
{
v.push_back(umap_ic[endId]);
if (endId == startId) break;
endId = pre[endId];
}
cout << "经过的最短路径为: " << endl;
for (int i = v.size() - 1; i >= 0; i--)
cout << v[i] << "->";
cout << t << endl;
}
void mune()
{
cout << "----------------------------------------------------" << endl;
cout << "1. 添加城市" << endl;
cout << "2. 删除城市" << endl;
cout << "3. 查询最短路径" << endl;
cout << "4. 查询相邻城市" << endl;
cout << "5. 修改两个城市之间的距离" << endl;
}
int main()
{
init();
mune();
int op = -1;
while (true)
{
cout << "请选择要进行的操作(输入为0结束程序): " << endl;
cin >> op;
if (op == 0) return 0;
switch (op)
{
case 1:
{
cout << "请输入你要添加的城市名字: " << endl;
string a; cin >> a;
if (add(a))
cout << "添加" << a << "城市成功" << endl;
else
cout << "城市已到达上限" << endl;
break;
}
case 2:
{
cout << "请输入你要删除的城市: " << endl;
string a; cin >> a;
if (delCity(a))
cout << "删除城市" << a << "成功" << endl;
else
cout << "删除城市失败，请检查输入的城市是否错在" << endl;
break;
}
case 3:
{
findShortestPath();
break;
}
case 4:
{
cout << "请输入城市: " << endl;
string a; cin >> a;
findAdjacencyPoint(a);
break;
}
case 5:
{
cout << "请输入你要修改的城市名字，及其要修改的距离" << endl;
string a, b; int w;
cin >> a >> b >> w;
modify(a, b, w);
break;
}
}
}
}
