本文主要是介绍poj 2502 subway (最短路)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
人走路的速度是10km/h，地铁的速度是40km/h
题目给出一个起点，一个终点，
以及几条地铁线路运行的站点。
题目给的点的做坐标单位是m
把速度统一为m/min
答案输出从起点到终点的时间，分钟数。
10km/h= 10000/60 m/min
40km/h= 40000/60 m/min
所有的点直接以步行的速度建边。
地铁线路两站相邻的以地铁速度建边
/************************************************ Author: fisty* Created Time: 2015/2/24 20:10:15* File Name : L.cpp*********************************************** */
#include <iostream>
#include <cstring>
#include <deque>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <algorithm>
using namespace std;
#define Debug(x) cout << #x << " " << x <<endl
#define Memset(x, a) memset(x, a, sizeof(x))
const int INF = 0x3f3f3f3f;
typedef long long LL;
typedef pair<int, int> P;
#define FOR(i, a, b) for(int i = a;i < b; i++)
#define MAX_N 2520
int n;
double G[MAX_N][MAX_N];
struct Point{int x;int y;
}p[MAX_N];
double walk(int i, int j){double l = sqrt((double)(p[i].x - p[j].x) * (p[i].x - p[j].x) + (double)(p[i].y - p[j].y) * (p[i].y - p[j].y));return l * 60 / 10000.0;
}
double subway(int i, int j){double l = sqrt((double)(p[i].x - p[j].x) * (p[i].x - p[j].x) + (double)(p[i].y - p[j].y) * (p[i].y - p[j].y));return l * 60.0 / 40000.0;
}
void solve(){for(int k = 1; k <= n; k++){for(int i = 1;i <= n; i++){for(int j = 1;j <= n; j++){G[i][j] = min(G[i][j], G[i][k] + G[k][j]);}}}
}
int main(){//freopen("in.cpp", "r", stdin);scanf("%d%d%d%d", &p[1].x, &p[1].y, &p[2].x, &p[2].y);G[1][2] = G[2][1] = walk(1, 2);int j = 0;n = 3;int a, b;while(scanf("%d%d",&a,&b) != EOF){ if(a == -1 && b == -1) j = 0; else{ p[n].x = a, p[n].y = b; for(int i = 1;i < n - j; i++){ G[i][n] = G[n][i] = walk(i,n); } for(int i = n-j; i < n; i++){ G[i][n] = G[n][i] = subway(i,n); } j = 1, n++; } } n--;solve();printf("%.0f\n", G[1][2]);return 0;
}
这篇关于poj 2502 subway (最短路)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
