传送门==>https://vjudge.net/problem/POJ-2253
POJ 编译器版本较低 有些会出现编译错误 但是无伤大雅
心得:
难点一:转换松弛操作
if (dis[v] > dis[u] + w)
dis[v] = dis[u] + w;
||
||
\/
if (dis[v] > max(dis[u], w))
dis[v] = max(dis[u], w);
难点二:建图不熟练
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
{
add(j, i, distant(p[i], p[j]));
add(i, j, distant(p[i], p[j]));
}
法一: Dijkstra + 邻接表 (邻接矩阵也可以 因为数据小)
#include <cmath>
#include <queue>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<double, int> gsl;
const int N = 210, M = 40010;
int T;
int h[N], e[M], ne[M], idx;// 邻接表
double dist[N], w[M]; // 到 dist[i] 的最小最大距离
bool st[N]; //也可以不需要 数据小无所谓的
struct gd
{
double x, y;
}gds[N];
void add(int a, int b, double c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
inline double gdd(gd a, gd b)
{
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
void Dijkstra()
{
memset(dist, 0x43, sizeof dist);
memset(st, 0, sizeof st);
dist[1] = 0;
priority_queue<gsl, vector<gsl>, greater<gsl>> heap;
heap.push(make_pair(0, 1));
while(heap.size())
{
int t = heap.top().second;
heap.pop();
if(st[t]) continue;
for(int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if(dist[j] > max(dist[t], w[i])) //重点 判断是否松弛成功
{
dist[j] = max(dist[t], w[i]);
heap.push(make_pair(dist[j], j));
//cout << j << ' ' << dist[j] << ' ';
}
}
//cout << endl;
st[t] = true;
}
}
int main()
{
int cnt = 1;
while(cin >> T, T)
{
memset(h, -1, sizeof h);
idx = 0;//不要忘了!!!
for(int i = 1; i <= T; i++)
{
int a, b;
cin >> gds[i].x >> gds[i].y;
}
for(int i = 1; i <= T; i ++) // 建图
{
for(int j = i + 1; j <= T; j ++)
{
add(i, j, gdd(gds[i], gds[j]));
add(j, i, gdd(gds[i], gds[j]));
}
}
Dijkstra();
printf("Scenario #%d\nFrog Distance = %.3lf\n\n", cnt ++, dist[2]);
}
return 0;
}
法二:SPFA + 邻接矩阵
#include <cmath>
#include <queue>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 210, M = 40010;
int T;
double g[N][N];// 邻接矩阵
double dist[N]; // 到 dist[i] 的最小最大距离
bool st[N];
struct gd
{
double x, y;
}gds[N];
inline double gdd(gd a, gd b)
{
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
void spfa()
{
memset(dist, 0x43, sizeof dist);
memset(st, 0, sizeof st);
dist[1] = 0;
queue<int> q;
q.push(1);
st[1] = true;
while(q.size())
{
int t = q.front();
q.pop();
st[t] = false;
for(int i = 1; i <= T; i ++)//扫描当前顶点i所有出边
{
if(dist[i] > max(dist[t], g[t][i])) //重点 判断是否松弛成功
{
dist[i] = max(dist[t], g[t][i]);
if(!st[i])
{
q.push(i);
st[i] = true;
}
}
}
}
}
int main()
{
int cnt = 1;
while(cin >> T, T)
{
for(int i = 1; i <= T; i++)
{
int a, b;
cin >> gds[i].x >> gds[i].y;
}
for(int i = 1; i <= T; i ++) // 建图
{
for(int j = i + 1; j <= T; j ++)
{
g[i][j] = gdd(gds[i], gds[j]);
g[j][i] = gdd(gds[i], gds[j]);
}
}
spfa();
printf("Scenario #%d\nFrog Distance = %.3lf\n\n", cnt ++, dist[2]);
}
return 0;
}