GYM-102501A Environment-Friendly Travel 图论 最短路

GYM-102501A Environment-Friendly Travel 图论 最短路

题意

给定一个起点，一个终点。

路程中会消耗二氧化碳。问在总路程不超过(B)的条件下，最小的二氧化碳排放量。

坐标以二维平面形式给出，二氧化碳排放即路程乘以交通工具的系数。

[交通方式 1leq Tleq 100 \点的个数 1leq Nleq 1000 \最大路程1leq Bleq 100 \交通系数1leq C_i leq 100 ]

分析

经过学长指导，这是经典的最短路模型。

由于带有限制，只需先以终点为源点，路程跑一遍最短路，再以起点为源点，二氧化碳跑一遍带有限制的最短路即可。

注意一直WA8，是因为最短路实现的时候要判断

if(u.dis != cost[u.id]) continue;

代码

struct Point {
    double x, y;
    Point(){}
    Point(double _x,double _y): x(_x),y(_y){}
};

ll Dis(Point a, Point b) {
    return ceil(sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)));
}

Point p[1000005];
ll c[100005];
ll d[1005][1005];
ll dis[1000005];
ll diss[1000005];
ll cost[1000005];

struct node {
    int id;
    ll dis;
    node(int _id, ll _dis) {
        id = _id;
        dis = _dis;
    }
    friend bool operator < (node a, node b) {
        return a.dis < b.dis;
    }
};

int n;
ll lim;

struct Edge {
    int v, w;
    Edge(int a, int b) {
        v = a;
        w = b;
    }
};
vector<Edge> e[1000005];

void dijstra1() {
    for (int i = 0; i <= n + 1; i++) dis[i] = inf;
    dis[n + 1] = 0;
    priority_queue<node> q;
    q.push(node(n + 1, 0));
    while (!q.empty()) {
        node u = q.top();
        q.pop();
        if (u.dis != dis[u.id]) continue;
        for (int i = 0; i < e[u.id].size(); i++) {
            Edge y = e[u.id][i];
            if (dis[y.v] > d[u.id][y.v] + dis[u.id]) {
                dis[y.v] = d[u.id][y.v] + dis[u.id];
                q.push(node(y.v, dis[y.v]));
            }
        }
    }
}

void dijstra2() {
    for (int i = 0; i <= n + 1; i++) diss[i] = inf, cost[i] = inf;
    diss[n] = 0;
    cost[n] = 0;
    priority_queue<node> q;
    q.push(node(n, 0));
    while (!q.empty()) {
        node u = q.top();
        q.pop();
        if (u.dis != cost[u.id]) continue;
        for (int i = 0; i < e[u.id].size(); i++) {
            Edge y = e[u.id][i];
            ll w = c[y.w] * d[y.v][u.id];
            //cout << diss[u.id] << ' ' << d[u.id][y.v] << ' ' << dis[y.v] << '
';
            if (diss[u.id] + d[u.id][y.v] + dis[y.v] > lim) continue;
            if (cost[y.v] > cost[u.id] + w) {
                diss[y.v] = diss[u.id] + d[u.id][y.v];
                cost[y.v] = cost[u.id] + w;
                q.push(node(y.v, cost[y.v]));
            }
        }
    }
}

int main() {
    double xx, yy, xxx, yyy;
    scanf("%lf%lf%lf%lf", &xx, &yy, &xxx, &yyy);
    lim = readll();
    c[0] = readll();
    int T = readint();
    for (int i = 1; i <= T; i++)
        c[i] = readll();
    n = readint();
    p[n] = Point(xx, yy);
    p[n + 1] = Point(xxx, yyy);
    for (int i = 0; i < n; i++) {
        scanf("%lf%lf", &p[i].x, &p[i].y);
        int m = readint();
        while (m--) {
            int j = readint();
            int ss = readint();
            e[i].push_back(Edge(j, ss));
            e[j].push_back(Edge(i, ss));
        }
    }
    for (int i = 0; i <= n + 1; i++)
        for (int j = i + 1; j <= n + 1; j++)
            d[i][j] = d[j][i] = Dis(p[i], p[j]);
    for (int i = 0; i < n; i++)
        e[n].push_back(Edge(i, 0)), e[n + 1].push_back(Edge(i, 0));
    dijstra1();
    dijstra2();
    if (d[n][n + 1] > lim) {
        puts("-1");
        return 0;
    }
    ll res = d[n][n + 1] * c[0];
    for (int i = 0; i < n; i++)
        res = min(res, cost[i] + d[i][n + 1] * c[0]);
    Put(res);
    
}