数算 兔子与樱花 图,最小权值路径的Floyd算法
程序员文章站
2022-07-13 07:58:22
...
兔子与樱花
兔子与樱花(10分)题目内容:很久很久之前,森林里住着一群兔子。有一天,兔子们希望去赏樱花,但当他们到了上野公园门口却忘记了带地图。现在兔子们想求助于你来帮他们找到公园里的最短路。
输入格式:
输入分为三个部分。
第一个部分有P+1行(P<30),第一行为一个整数P,之后的P行表示上野公园的地点。
第二个部分有Q+1行(Q<50),第一行为一个整数Q,之后的Q行每行分别为两个字符串与一个整数,表示这两点有直线的道路,并显示二者之间的矩离(单位为米)。
第三个部分有R+1行(R<20),第一行为一个整数R,之后的R行每行为两个字符串,表示需要求的路线。
输出格式:
输出有R行,分别表示每个路线最短的走法。其中两个点之间,用->(矩离)->相隔。
输入样例:
6
Ginza
Sensouji
Shinjukugyoen
Uenokouen
Yoyogikouen
Meijishinguu
6
Ginza Sensouji 80
Shinjukugyoen Sensouji 40
Ginza Uenokouen 35
Uenokouen Shinjukugyoen 85
Sensouji Meijishinguu 60
Meijishinguu Yoyogikouen 35
2
Uenokouen Yoyogikouen
Meijishinguu Meijishinguu
输出样例:
Uenokouen->(35)->Ginza->(80)->Sensouji->(60)->Meijishinguu->(35)->Yoyogikouen
Meijishinguu
#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <cstring>
using namespace std;
map<string,int> addrname;
int len[40][40];
int path[40][40] = { 0 };
int flen[40][40]; //记录原始长度
int main()
{
int p, q, r;
cin >> p;
string name;
for (int i = 1; i <= p; i++)
for (int j = 1; j <= p; j++)
{
if (i == j)
{
len[i][j] = 0;
path[i][j] = i;
}
else
{
len[i][j] = 9999;
path[i][j] = -1;
}
}
for (int i = 1; i <= p; i++)
{
cin >> name;
addrname.insert(make_pair(name, i));
}
cin >> q;
string v1, v2;
int dis;
while (q--)
{
cin >> v1 >> v2;
cin >> dis;
len[addrname[v1]][addrname[v2]] = dis;
flen[addrname[v1]][addrname[v2]] = dis;
path[addrname[v1]][addrname[v2]] = addrname[v1];
len[addrname[v2]][addrname[v1]] = dis;
flen[addrname[v2]][addrname[v1]] = dis;
path[addrname[v2]][addrname[v1]] = addrname[v2];
}
for (int v = 1; v <= p; v++)
{
for (int i = 1; i <= p; i++)
for (int j = 1; j <= p; j++)
{
if (len[i][v] + len[v][j] < len[i][j])
{
len[i][j] = len[i][v] + len[v][j];
path[i][j] = path[v][j];
}
}
}
cin >> r;
while (r--)
{
string b, e;
cin >> b >> e;
while (b != e)
{
cout << b << "->(";
cout << flen[addrname[b]][path[addrname[e]][addrname[b]]] << ")->";
map<string, int>::iterator p = addrname.begin();
for (p; p != addrname.end(); ++p)
{
if (p->second == path[addrname[e]][addrname[b]])
{
b = p->first;
break;
}
}
}
cout << e << endl;
}
return 0;
}
上一篇: BAT脚本批量修改文件名