GroupBlog

题意

小明步行的速度是10km/h，地铁速度是40km/h，给定家和学校的坐标，再给定多条地铁线路站点的坐标，问小明从家到学校所需的最短时间

思路

典型的最短路，直接套用dijkstra就行，此题在读入数据上麻烦一点。
还有一个重要问题，导致我茫然wrong了好几次。
因为我是将每条地铁线路的站点读入后，便对这条线的站点两两之间按照40km来赋权值。但忽略了一个问题，地铁线路不一定是直的，如果是弯的呢，那么这样求出来的权值就会比实际权值要小。所以只能对同一线路的两两相邻站点进行赋值，才符合逻辑。

代码

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
using namespace std;

const int N = 209;
const int MAX = 0x3f3f3f3f;
int dx[N], dy[N];
double v[N][N];
bool vis[N];
double dis[N];

double dijkstra(int n)
{
    memset(vis, 0, sizeof(vis));
    for(int i=1; i<n; i++)
        dis[i] = v[0][i];
    dis[0] = 0;
    vis[0] = 1;
    for(int i=1; i<n; i++)
    {
        int x = -1;
        double max = MAX;
        for(int j=0; j<n; j++)
        {
            if(!vis[j] && dis[j] < max)
                max = dis[x = j];
        }
        if(x == -1)
            break;
        vis[x] = 1;
        for(int j=0; j<n; j++)
            if(!vis[j] && dis[j] > max + v[x][j])
                dis[j] = max + v[x][j];
    }
    return dis[1];
}

int main()
{
    scanf("%d%d%d%d", &dx[0], &dy[0], &dx[1], &dy[1]);
    int t, pos;
    t = pos = 2;
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
            v[i][j] = MAX;
    while(~scanf("%d%d", &dx[pos], &dy[pos]))
    {
        pos++;
        while(~scanf("%d%d", &dx[pos], &dy[pos]) && dx[pos] != -1 && dy[pos] != -1)
        {
            v[pos-1][pos] = v[pos][pos-1] =
                60*sqrt((dx[pos]-dx[pos-1])*(dx[pos]-dx[pos-1])
                +(dy[pos]-dy[pos-1])*(dy[pos]-dy[pos-1]))/40000.0;
            pos++;
        }
    }
    for(int i=0; i<pos; i++)
    {
        for(int j=i+1; j<pos; j++)
            v[i][j] = v[j][i] =
                min(v[i][j],
                    60*sqrt((dx[i]-dx[j])*(dx[i]-dx[j])
                            +(dy[i]-dy[j])*(dy[i]-dy[j]))/10000.0);
    }
    printf("%.0f\n", dijkstra(pos));
    return 0;
}