侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【单源最短路】Car的旅行路线

GabrielxD
2023-04-26 / 0 评论 / 0 点赞 / 196 阅读 / 2,136 字
温馨提示:
本文最后更新于 2023-08-04,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

P1027 [NOIP2001 提高组] Car 的旅行路线

试题 算法训练 Car的旅行路线


题目描述

又到暑假了,住在城市 A 的 Car 想和朋友一起去城市旅游。
她知道每个城市都有 44 个飞机场,分别位于一个矩形的 44 个顶点上,同一个城市中两个机场之间有一条笔直的高速铁路,第 ii 个城市中高速铁路了的单位里程价格为 TiT_i,任意两个不同城市的机场之间均有航线,所有航线单位里程的价格均为 tt

图例(从上而下)

机场
高速铁路
飞机航线

注意:图中并没有标出所有的铁路与航线。

那么 Car 应如何安排到城市B的路线才能尽可能的节省花费呢?她发现这并不是一个简单的问题,于是她来向你请教。

找出一条从城市 A 到 B 的旅游路线,出发和到达城市中的机场可以任意选取,要求总的花费最少。

输入格式

第一行为一个正整数 nn,表示有 nn 组测试数据。

每组的第一行有 44 个正整数 s,t,A,Bs,t,A,B

SS 表示城市的个数,tt 表示飞机单位里程的价格,AABB 分别为城市A,B 的序号。

接下来有 SS 行,其中第 ii 行均有 77 个正整数xi1,yi1,xi2,yi2,xi3,yi3,Tix_{i1},y_{i1},x_{i2},y_{i2},x_{i3},y_{i3},T_i ,这当中的 (xi1,yi1x_{i1},y_{i1}),(xi2,yi2x_{i2},y_{i2}),(xi3,yi3x_{i3},y_{i3})分别是第 ii 个城市中任意 33 个机场的坐标,TiT_i 为第 ii 个城市高速铁路单位里程的价格。

输出格式

共有 nn 行,每行 11 个数据对应测试数据。
保留一位小数。

样例 #1

样例输入 #1

1
3 10 1 3
1 1 1 3 3 1 30
2 5 7 4 5 2 1
8 6 8 8 11 6 3

样例输出 #1

47.5

提示

【数据范围】

对于 100%100\% 的数据,1n101\le n \le 101S1001\le S \le 1001A,BS1\le A,B \le S

【题目来源】

NOIP 2001 提高组第四题

解题

方法一:SPFA算法

思路

本题是单纯的单源最短路问题,但是建图比较麻烦:

先利用已有的三个点的坐标,根据勾股定理的逆定理,判断出直角边:

image-20230426213921763

例如上图中若有 AB2+BC2=AC2AB^2 + BC^2 = AC^2 则说明 AB,BCAB, BC 为直角边。

然后根据矩形对边平行的性质仿照 BAB \to A 移动 CDC \to D 就能得到 DD 点的坐标:

image-20230426214111381

因为“任意两个不同城市的机场之间均有航线”、“同一个城市中两个机场之间有一条笔直的高速铁路”,那么每一个顶点都可以与其它所有顶点连一条无向边,也就是说这是一个完全图,但题目给出的数据范围最多有 S=100S=100 个城市,那么最多会连 2×4S(4S1)=3192002 \times 4S(4S-1) = 319200 条边,所以用邻接矩阵或者邻接表存图都可以。

注意算边权的时候,如果两点在同一城市,就要用距离乘以该城市的高速铁路价格 TiT_i ,否则,走的是飞行航线,需乘以航线单价 tt

代码

不存图,边做SPFA边算边权:

import java.util.*;
import java.io.*;

public class Main {
    static final int INF = 0x3f3f3f3f;
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static int n, T, A, B;
    static int[][] pts;
    static int[] ts;

    static int getSquDist(int x1, int y1, int x2, int y2) {
        int dx = x1 - x2, dy = y1 - y2;
        return dx * dx + dy * dy;
    }

    static double getDist(int x1, int y1, int x2, int y2) {
        return Math.sqrt(getSquDist(x1, y1, x2, y2));
    }

    static int[] getD(int ax, int ay, int bx, int by, int cx, int cy) {
        int squAB = getSquDist(ax, ay, bx, by);
        int squBC = getSquDist(bx, by, cx, cy);
        int squAC = getSquDist(ax, ay, cx, cy);
        if (squAB + squBC == squAC) return new int[]{cx + ax - bx, cy + ay - by, 0};
        else if (squAB + squAC == squBC) return new int[]{ax + bx - ax, cy + by - ay, 0};
        else if (squBC + squAC == squAB) return new int[]{ax + bx - cx, ay + by - cy, 0};
        return null;
    }

    static double spfa(int src, int dest) {
        double[] dists = new double[n * 4 + 1];
        Arrays.fill(dists, INF);
        Queue<Integer> que = new LinkedList<>();
        boolean[] has = new boolean[n * 4 + 1];
        int st = (src - 1) * 4 + 1, ed = st + 4;
        for (int i = st; i < ed; ++i) {
            dists[i] = 0.0;
            que.offer(i);
            has[i] = true;
        }
        while (!que.isEmpty()) {
            int u = que.poll();
            has[u] = false;
            int x = pts[u][0], y = pts[u][1];
            for (int v = 1; v <= n * 4; ++v) {
                if (v == u) continue;
                double d = getDist(x, y, pts[v][0], pts[v][1]);
                double w = pts[u][2] == pts[v][2] ? ts[pts[u][2]] * d : T * d;
                if (dists[u] + w < dists[v]) {
                    dists[v] = dists[u] + w;
                    if (!has[v]) {
                        que.offer(v);
                        has[v] = true;
                    }
                }
            }
        }
        double mn = INF;
        st = (dest - 1) * 4 + 1; ed = st + 4;
        for (int i = st; i < ed; ++i) mn = Math.min(mn, dists[i]);
        return mn;
    }

    static void solve() throws IOException {
        in.nextToken(); n = (int) in.nval;
        in.nextToken(); T = (int) in.nval;
        in.nextToken(); A = (int) in.nval;
        in.nextToken(); B = (int) in.nval;
        pts = new int[n * 4 + 1][3];
        ts = new int[n + 1];
        for (int i = 1; i <= n * 4; i += 4) {
            int city = i / 4 + 1;
            in.nextToken(); pts[i][0] = (int) in.nval;
            in.nextToken(); pts[i][1] = (int) in.nval;
            in.nextToken(); pts[i + 1][0] = (int) in.nval;
            in.nextToken(); pts[i + 1][1] = (int) in.nval;
            in.nextToken(); pts[i + 2][0] = (int) in.nval;
            in.nextToken(); pts[i + 2][1] = (int) in.nval;
            in.nextToken(); ts[city] = (int) in.nval;
            int[] pos = getD(pts[i][0], pts[i][1], pts[i + 1][0], pts[i + 1][1], pts[i + 2][0], pts[i + 2][1]);
            pts[i + 3] = pos;
            pts[i][2] = pts[i + 1][2] = pts[i + 2][2] = pts[i + 3][2] = city;
        }
        System.out.printf("%.1f\n", spfa(A, B));
    }

    public static void main(String[] args) throws IOException {
        in.nextToken(); int t = (int) in.nval;
        while (t-- > 0) solve();
    }
}

邻接表存图:

import java.util.*;
import java.io.*;

public class Main {
    static final int INF = 0x3f3f3f3f;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer in = new StreamTokenizer(br);
    static int s, T, A, B;
    static int n, m;
    static int[][] pts;
    static int[] ts;
    static int[] h, e, ne;
    static double[] w;
    static int idx;

    static int getSquDist(int x1, int y1, int x2, int y2) {
        int dx = x1 - x2, dy = y1 - y2;
        return dx * dx + dy * dy;
    }

    static double getDist(int x1, int y1, int x2, int y2) {
        return Math.sqrt(getSquDist(x1, y1, x2, y2));
    }

    static void add(int a, int b, double c) {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
    }

    static int[] getD(int ax, int ay, int bx, int by, int cx, int cy) {
        int squAB = getSquDist(ax, ay, bx, by);
        int squBC = getSquDist(bx, by, cx, cy);
        int squAC = getSquDist(ax, ay, cx, cy);
        if (squAB + squBC == squAC) return new int[]{cx + ax - bx, cy + ay - by, 0};
        else if (squAB + squAC == squBC) return new int[]{ax + bx - ax, cy + by - ay, 0};
        else if (squBC + squAC == squAB) return new int[]{ax + bx - cx, ay + by - cy, 0};
        return null;
    }

    static double spfa(int src, int dest) {
        double[] dists = new double[n + 1];
        Arrays.fill(dists, INF);
        Queue<Integer> que = new LinkedList<>();
        boolean[] has = new boolean[n + 1];
        int st = (src - 1) * 4 + 1, ed = st + 4;
        for (int i = st; i < ed; ++i) {
            dists[i] = 0.0;
            que.offer(i);
            has[i] = true;
        }
        while (!que.isEmpty()) {
            int u = que.poll();
            has[u] = false;
            for (int i = h[u]; i != -1; i = ne[i]) {
                int v = e[i];
                if (dists[u] + w[i] < dists[v]) {
                    dists[v] = dists[u] + w[i];
                    if (!has[v]) {
                        que.offer(v);
                        has[v] = true;
                    }
                }
            }
        }
        double mn = INF;
        st = (dest - 1) * 4 + 1; ed = st + 4;
        for (int i = st; i < ed; ++i) mn = Math.min(mn, dists[i]);
        return mn;
    }

    static void solve() throws IOException {
        in.nextToken(); s = (int) in.nval;
        in.nextToken(); T = (int) in.nval;
        in.nextToken(); A = (int) in.nval;
        in.nextToken(); B = (int) in.nval;
        n = s * 4; m = 2 * n * n;
        pts = new int[n + 1][3];
        ts = new int[s + 1];
        h = new int[n + 1];
        Arrays.fill(h, -1);
        e = new int[m];
        ne = new int[m];
        w = new double[m];
        for (int i = 1; i <= n; i += 4) {
            int city = i / 4 + 1;
            in.nextToken(); pts[i][0] = (int) in.nval;
            in.nextToken(); pts[i][1] = (int) in.nval;
            in.nextToken(); pts[i + 1][0] = (int) in.nval;
            in.nextToken(); pts[i + 1][1] = (int) in.nval;
            in.nextToken(); pts[i + 2][0] = (int) in.nval;
            in.nextToken(); pts[i + 2][1] = (int) in.nval;
            in.nextToken(); ts[city] = (int) in.nval;
            int[] pos = getD(pts[i][0], pts[i][1], pts[i + 1][0], pts[i + 1][1], pts[i + 2][0], pts[i + 2][1]);
            pts[i + 3] = pos;
            pts[i][2] = pts[i + 1][2] = pts[i + 2][2] = pts[i + 3][2] = city;
        }
        for (int u = 1; u <= n; ++u) {
            int cu = pts[u][2];
            for (int v = 1; v <= n; ++v) {
                double d = getDist(pts[u][0], pts[u][1], pts[v][0], pts[v][1]);
                double w = d * (cu == pts[v][2] ? ts[pts[u][2]] : T);
                add(u, v, w); add(v, u, w);
            }
        }
        System.out.printf("%.1f\n", spfa(A, B));
    }

    public static void main(String[] args) throws IOException {
        in.nextToken(); int t = (int) in.nval;
        while (t-- > 0) solve();
    }
}
0

评论区