最短路径手写

#include <iostream>
#include <vector>
#include <climits>
using namespace std;
class node {
public:
    int x;
    int y;
    node(int x, int y) {
        this->x = x;
        this->y = y;
    }
    node() {x= 0; y = 0;}

};
int cal(node& a, node& b) {
    return abs(a.x - b.x) + abs(a.y - b.y);
}
int main() {
    int n ;
    cin >> n;
    vector<bool> flag(n ,false);
    vector<node> s;
    vector<int> dist(2 * n + 2, 0);
    int s_x, s_y, d_x, d_y;
    cin >> s_x >> s_y >> d_x >> d_y;

    s.push_back(node(s_x, s_y));
    s.push_back(node(d_x, d_y));
    vector<vector<int>> v(2 * n + 2, vector<int>(2 * n + 2, 0));
    for (int i = 0; i < n; i++) {
        int x1, y1, x2, y2, d;
        cin >> x1 >> y1 >> x2 >> y2 >> d;
        s.push_back(node(x1, y1));
        s.push_back(node(x2, y2));
        v[2 + 2*i][2 + 2 * i + 1] = d;
        v[2 + 2 * i + 1] [2 + 2 * i] = d;
    }
    for (int i = 0; i < 2* n  + 1; i++) {
        for (int j = i + 1; j < 2 *n + 2; j++) {
            if (v[i][j] == 0) {
                v[i][j] = cal(s[i], s[j]);
                v[j][i] = v[i][j];
            }
        }
    }
//    for (int i = 0; i < 2*n + 2; i++) {
//        for (int j = 0; j < 2* n + 2; j++) {
//            cout << v[i][j] << " ";
//        }
//        cout << endl;
//    }
    int len = 2 * n + 2;
    for (int i = 0; i < len; i++) {
        dist[i] = v[0][i];
    }
    flag[0] = true;
    int minval, u;
    for (int i = 0; i < len - 1; i++) {
        minval = 99999;
        for (int j = 0; j < len; j++) {
            if (flag[j] == false && dist[j] < minval) {
                minval = dist[j];
                u = j;
            }
        }
        // cout << u << endl;
        flag[u] = true;
        for (int k = 0; k < len; k++) {
            if (v[u][k] < 99999) {
                if (dist[k] > dist[u] + v[u][k]) {
                    dist[k] = dist[u] + v[u][k];
                }
            }
        }
    }
    cout << dist[2] << endl;
    return 0;
}

三星的笔试题代码基本可以如此操作，难点就是要手写dijkstra算法题