欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数算 兔子与樱花 图,最小权值路径的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;
}
相关标签: 数算