2021美团春招笔试（数据开发）

题目1：
小美和小团在n行m列网格的图玩游戏，他们规定，有k个五元组（x，y，u，v,w），由x行y列网格向u行v列网格移动时花费为w，其它移动方式一律不合法，同时为了降低游戏难度，保证x≤u，y≤v.现在请求你从1行1列到n行列网格所需最小花费是多少？
输入描述：

第一行三个数n,m,k,表示行数、列数和五元组的个数。
接下来k行，每行5个数xi、yi、ui、vi、wi；含义如上文所述，保证给出各点有效且合法。
1≤n,m≤500,0≤wi≤100,0 ≤ k ≤ 50000

输出：

输出一个整数，表示答案，若无法从1行1列到n行m列，输出整数-1.

样例输入：

5 4 3
1 1 2 2 1
1 1 5 4 4
2 2 5 4 1

样例输出：

2

解题思路：
此题典型的求两点之间最短路径问题，使用dijkstra算法。

按照第二种思路，需要手从k*2个点中动统计出有多少点不重复点，可以使用set或者map集合进行去重统计处理。
实现：

#include<iostream>
#include<map>
#define N 5000
using namespace std;
//map中如果key值 
typedef struct MyDouble {
    int one;
    int two;
    //map中key值使用多个元素做key，使用的符合结构体，
    //在结构体里面需要重写"<"操作符，map中key只有一个元素时，
    // key在map中按照生序排列 
    bool operator<(const MyDouble& d)const {
        if(d.one  < one && d.two < two){
            return true;
        }
        else if (d.one  < one && d.two > two) {
            return false;
        }
        else {
            return false;
        }
    }

}MyDouble;
typedef struct{
    int city;
}One;

int edge[N][N],weight[N],disp[N];
bool visited[N] = {false};
const int inf = 99999;

int main(){

    int prev[N];

    fill(edge[0],edge[0]+N*N,inf);
    fill(disp,disp+N,inf);



    int temp1,temp2,temp3;
    cin>>temp1>>temp2>>temp3;

    //转换
    int n,m;
    n = 0;
    m = temp3;

    //使用map去重统计一共多少个点 
    map<MyDouble,int> mp;
    int x,y,u,v,w;
    int a,b,c;
    for(int i  = 0;i < m;i++){
        cin>>x>>y>>u>>v>>w;
        MyDouble city1 = {x,y};
        if(mp.count(city1)<=0){
            mp[city1] = n;
            a = n;
            n++;
        }else{
            a = mp[city1];
        }
        MyDouble city2 = {u,v};
        if(mp.count(city2)<=0){
            mp[city2] = n;
            b = n;
            n++;
        }else{
            b = mp[city2];
        }
        c = w;
        edge[a][b] = edge[b][a] = c;
    }
    for(int i  = 0;i < N;i++){
        prev[i] = i;
        edge[i][i] = 0;
    }

    //使用dijkstra算法求{1,1}到其它点最短距离 
    MyDouble city4 = {1,1};
    int start_point = mp[city4];
    disp[start_point] = 0;
    for(int i = 0;i < n;i++){
        int u = -1,min = inf;
        for(int j = 0;j < n;j++){
            if(visited[j] == false&& disp[j] <= min){
                u = j;
                min = disp[j];
            }
        }
        if(u == -1)
          break;
        visited[u] = true;
        for(int v = 0; v < n;v++){
            if(visited[v] == false&& edge[u][v] != inf){
                if(disp[u] + edge[u][v] < disp[v]){
                    disp[v] = disp[u] +edge[u][v];
                    prev[v] = u;
                }
            }
        } 
    }

    //输出（1,1）到（5,4）最短距离 
    MyDouble city3 = {temp1,temp2};
    int end_point = mp[city3];
    if(disp[end_point] == inf){//没有路径
        cout<<-1<<endl;
    }else{//有路径
            cout<<disp[end_point]<<endl;
    }

    return 0;
}

扩展：此题可以对应实际生活中根据地点地图定位（维度，经度），计算两个地点之间最短距离。