HDU2923-最短路-floyd

原题链接

特别坑的一道题，卡了我好几个小时

1. 车辆是需要在多个地方拉回来的，一次只能拉一辆，所以直接将地方都存起来
2. 在拉车过程中，需要从起点到拉车地方 ，从拉车点到起点，两条路径是会不同的
3. 最坑的一点，坏车的数据是小于1000，需要注意

关于字符串处理

• 地名直接用map可以解决，给每个地名起一个独一无二的标号
• 而关于路径的方向，网上很多博主是用字符串接收，再去分离中间的数字
  其实这样特别麻烦，数字左右两边就只有两个字符，所以直接用四个char去接收，
  中间加个数字，这样就可以直接区分出来了

map的用法

map<string,int> map; //map[a]=b, 表示a的类型是字符串，b为整型变量
对于没有出现过的字符串，map["字符串"]的值为0
利用这个性质，我们可以在接收每一个地名的时候，用map判断一下它们的值
值为0，表示该地名是第一次出现的
值不为0，则直接用它的标号存储即可

#include <iostream>
#include <map>
#include <cstring>
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

const int N=1100;

int g[N][N];//存储城市之间的最短路径 
int s[N];//存储废车的地址 
int n,c,r;
string a,b;

int main()
{
    map<string,int> map;//string存储地名，int存储地名对应的编号 
    int num=1;
    while(cin>>n>>c>>r&&(n+c+r)){
        memset(g,0x3f,sizeof g);
        int cnt=1;//地名的标号从1开始 
        map.clear();//清除上一次map的所有信息 
        for(int i=0;i<=c;i++){//第一个地名对应的是修车厂，其他是废车所在地 
            cin >> a;
            
            //如果当前地点是第一次接收，则给它一个唯一编号
            if(map[a]==0) map[a]=cnt++; 
            s[i]=map[a];//将地点标号存储在s 
        }
        
        for(int i=0;i<r;i++){
            int c;
            char ch1,ch2,ch3,ch4;
            cin >> a >> ch1 >> ch2 >> c >> ch3 >> ch4 >> b;
            //如果当前地点是第一次接收，则给它一个唯一编号
            if(map[a]==0) map[a]=cnt++;
            if(map[b]==0) map[b]=cnt++;
            
            //判断方向 
            if(ch1=='<') g[map[b]][map[a]]=min(g[map[b]][map[a]],c);
            if(ch4=='>') g[map[a]][map[b]]=min(g[map[a]][map[b]],c);
        }
      //floyd算法
        for(int k=1;k<cnt;k++){
            for(int i=1;i<cnt;i++){
                for(int j=1;j<cnt;j++){
                    g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
                }
            }
        }
        
        //res存储所花的时间 
        int res=0;
        
        //s[0]是修车厂，s[1~c]是废车地点 
        for(int i=1;i<=c;i++){
            //需要加上从修车厂到废车点所花的时间，以及回到修车厂所花时间 
            res+=g[s[0]][s[i]]+g[s[i]][s[0]];
        }
        cout<<num++<<". "<<res<<endl;
    }
    return 0;
}