目录
Subway(使用优先队列的dijkstar)
题目题目大意思路注意代码
Subway(使用优先队列的dijkstar)
题目
poj 2502 Subway
题目大意
给定起点与终点，中间有几条地铁线路，可以选择步行或者乘地铁，求最短的时间花费。
思路
最重要的就是建图。我这里使用的是邻接表（vector数组实现，这样即使有重边也无所谓）。实际上所有点都是可以步行到达，只是耗费更多时间而已。
注意
使用邻接表时不能使用used标记，因为存在重边。
代码
#include <algorithm>
#include <iostream>
#include <vector>
#include <memory.h>
#include <queue>
#include <cmath>
#define maxn 206
#define INF 0x3f3f3f
using namespace std;
struct node
{
double x, y;
node(double xx, double yy) { x = xx, y = yy; }
node() {}
} es[maxn];
int len = 0;
double d[maxn];
int inq[maxn];
vector<pair<int, double>> eg[maxn];
typedef pair<double, int> p;
void init()
{
for (int i = 1; i <= maxn; i++)
inq[i] = 0;
for (int i = 1; i <= maxn; i++)
eg[i].clear();
for (int i = 1; i <= maxn; i++)
d[i] = INF;
}
double getdic(double x1, double y1, double x2, double y2)
{
return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
void dijkstar()
{
priority_queue<p, vector<p>, greater<p>> q;
d[1] = 0;
q.push(p(d[1], 1));//将起点推入队列
while (!q.empty())
{
p cur = q.top();//取出最近的节点
int now = cur.second;//该节点的id
inq[now]=0;//取消标记
q.pop();
for (int i = 0; i < eg[now].size(); i++)//遍历所有该节点链接的点
{
int v = eg[now][i].first;
if (d[v] > eg[now][i].second + d[now])
{
d[v] = eg[now][i].second + d[now];
if (inq[v])//添加标记，优化
continue;
inq[v] = 1;
q.push(p(d[v], v));
}
}
}
}
int main()
{
init();
double x, y;
cin >> x >> y;
es[++len] = node(x, y);
cin >> x >> y;
es[++len] = node(x, y);
int last = 2;
while (cin >> x >> y) //地铁的路线
{
if (x == -1.0)
{
for (int i = last + 1; i < len; i++)
{
double dis = getdic(es[i].x, es[i].y, es[i + 1].x, es[i + 1].y) / 40000.0;
eg[i].push_back(make_pair(i + 1, dis));
eg[i + 1].push_back(make_pair(i, dis));
}
last = len;
continue;
}
es[++len] = node(x, y);
}
for (int i = 1; i <= len; i++)//补全所有可以步行的边
for (int j = i + 1; j <= len; j++)
{
double dis = getdic(es[i].x, es[i].y, es[j].x, es[j].y) / 10000.0;
eg[i].push_back(make_pair(j, dis));
eg[j].push_back(make_pair(i, dis));
}
dijkstar();
cout << int(d[2] * 60 + 0.5) << endl;
}
转载于:https://www.cnblogs.com/tttfu/p/11233044.html
相关资源：JAVA上百实例源码以及开源项目
