gym101124 L. Subway（最短路，dijkstra板子）

本文主要是介绍gym101124 L. Subway（最短路，dijkstra板子），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

https://codeforces.com/gym/101124

题意：

最短路

思路：

建完图，上dijkstra板子即可

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second

const int N = 210;

double g[N][N];  //存储每条边
double dist[N];
bool st[N];
double dijkstra(int n)
{ //求1号点到n号点的最短路，如果不存在则返回-1
    fill(dist, dist+n+5, 1e9);
    dist[1] = 0;
    for(int i = 0; i < n - 1; i++)
    {
        int t = -1;
        for(int j = 1; j <= n; j++)
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        for(int j = 1; j <= n; j++)
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        st[t] = true;
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

pair<double, double> p[N]; int n;
double wwalk(pair<double, double> t1, pair<double, double> t2)
{return sqrt((t1.x-t2.x)*(t1.x-t2.x)+(t1.y-t2.y)*(t1.y-t2.y))/(10/3.6); }
double wsubway(pair<double, double> t1, pair<double, double> t2)
{return sqrt((t1.x-t2.x)*(t1.x-t2.x)+(t1.y-t2.y)*(t1.y-t2.y))/(40/3.6); }

signed main()
{
    int xx, yy, xf, yf; cin >> xx >> yy >> xf >> yf; p[++n] = {xx, yy};
    bool flag = 0;
    while(cin >> xx >> yy)
    {
        if(xx == -1 && yy == -1) {flag = 0; continue; }
        p[++n] = {xx, yy};
        for(int i = 1; i < n; i++)
            g[i][n] = g[n][i] = wwalk(p[i], p[n]);
        if(flag)
            g[n-1][n] = g[n][n-1] = wsubway(p[n-1], p[n]);
        flag = 1;
    }
    p[++n] = {xf, yf};
    for(int i = 1; i < n; i++)
        g[i][n] = g[n][i] = wwalk(p[i], p[n]);

    cout << fixed << setprecision(0) << dijkstra(n)/60;

    return 0;
}

这篇关于gym101124 L. Subway（最短路，dijkstra板子）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！