poj-2253-poj-1797_最短路练习概述分析与思路代码小结

---

title: poj-2253-poj-1797_最短路练习
date: 2018-11-17 11:48:51
tags:

• acm
• 刷题
  categories:

• ACM-最短路

概述

一道最短路的变形题，，虽然说解法不止这一种，，

这道题看了好久都没看懂题意，，不知到在求什么，，，最后迫不得已去看了别人的思路，，理清思路之后，，代码就好写了，，，只需在原来的dijkstra板子上改一改就行了，，

补：第二道题和第一道题类似，，再改一改就行了，，

分析与思路

这道题的大致题意就是：给你n块石头的坐标，，然后问你从第一块石头到第二块石头的所有可到的m条路径中，，那m条最长的路中的最小的，，

所以分两步计算，，，

• 先求 i->j m条路径中每条路径中的最大值，，

• 然后求这m个最大值中的最小值，，，

按照这个思路，，dijkstra中的松弛条件就要改成

(dis[v] = min(dis[v] , max(dis[u] , w[u][v])))

• dis[v]表示原点1到v的最大路中的最小值，，同理dis[u]也一样
• w[u][v]表示u->v的权值
• 求1->v的最大路中的最小值就等于 之前从别的路径到v中求得的最大路中的最小值 与 1->u->v这条路径中的最大路中的最小值，，（也就是 1->u 中最大路的最小值 和 u->v的权值相比较取最大的） 的最小值

对了，，网上看到的别人的博客大多都是用邻接矩阵实现的，，，然后我尝试用邻接表实现的，，，注意对数据的处理，，，因为是给的点的坐标而不是点的编号，，，所以是每个点之间都有路径，，，最后，，用邻接表是实现记得处理完一组数据要把邻接表清空，，，
还有输出在poj上g++用%.3f

第二道题就是前一道的反过来，，，求所有路径中最小值的最大值，，，

代码

//poj-2253
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 1e3 + 5;
const double inf = 0x3f3f3f3f;
struct node
{
int v;
double c;
node(){}
node(int _v , double _c):v(_v) , c(_c){}
bool operator < (const node &r) const
{
return c > r.c;
}
};
struct edge
{
int v;
double w;
edge(int _v = 0 , double _w = 0):v(_v) , w(_w){}
};
vector<edge> e[maxn];
double dis[maxn];
bool vis[maxn];
int n;
void addedge(int u , int v , double w)
{
e[u].push_back(edge(v , w));
}
void dijkstra()
{
memset(vis , false , sizeof vis);
for(int i = 1; i <= n; ++i)
dis[i] = inf;
dis[1] = 0;
priority_queue<node> q;
while(!q.empty())
q.pop();
q.push(node(1 , 0));
node t;
while(!q.empty())
{
t = q.top();q.pop();
int u = t.v;
if(vis[u])
continue;
vis[u] = true;
for(int i = 0; i < e[u].size(); ++i)
{
int v = e[t.v][i].v;
double w = e[u][i].w;
if(!vis[v])
{
dis[v] = min(dis[v] , max(dis[u] , w));
q.push(node(v , dis[v]));
}
}
}
}
int main()
{
int q = 1;
while(scanf("%d" , &n) != EOF && n)
{
double x[maxn] , y[maxn];
for(int i = 1; i
<= n; ++i)
scanf("%lf%lf" , &x[i] , &y[i]);
for(int i = 1; i < n; ++i)
for(int j = i + 1; j <= n; ++j)
{
double w = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
addedge(i , j , w);
addedge(j , i , w);
}
dijkstra();
printf("Scenario #%dnFrog Distance = %.3lfnn" , q++ , dis[2]);
for(int i = 0; i < maxn; ++i)
e[i].clear();
}
}

//1797
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 1e3 + 5;
const int inf = 0x3f3f3f3f;
struct node
{
int v;
int c;
node(){}
node(int _v , int _c):v(_v) , c(_c){}
bool operator < (const node &r) const
{
return c < r.c;
}
};
struct edge
{
int v;
int w;
edge(int _v = 0 , int _w = 0):v(_v) , w(_w){}
};
vector<edge> e[maxn];
int dis[maxn];
bool vis[maxn];
int n , m;
void addedge(int u , int v , int w)
{
e[u].push_back(edge(v , w));
}
void dijkstra()
{
memset(vis , false , sizeof vis);
for(int i = 1; i <= n + 1; ++i)
dis[i] = 0;
dis[1] = inf;
priority_queue<node> q;
while(!q.empty())
q.pop();
q.push(node(1 , inf));
node t;
while(!q.empty())
{
t = q.top();q.pop();
int u = t.v;
if(vis[u])
continue;
vis[u] = true;
for(int i = 0; i < e[u].size(); ++i)
{
int v = e[t.v][i].v;
int w = e[u][i].w;
if(!vis[v])
{
dis[v] = max(dis[v] , min(dis[u] , w));
q.push(node(v , dis[v]));
}
}
}
}
int main()
{
int q = 1;int t;scanf("%d" , &t);
while(t--)
{
scanf("%d%d" , &n , &m);
int u , v , w;
for(int i = 1; i <= m; ++i)
{
scanf("%d%d%d" , &u , &v , &w);
addedge(u , v , w);
addedge(v , u , w);
}
dijkstra();
printf("Scenario #%d:n%dnn" , q++ , dis[n]);
for(int i = 0; i < maxn; ++i)
e[i].clear();
}
}
第二道题思路是对的，，，最后的输出忘记加:wa了4次，，，一直以为是自己的邻接表+优先队列写的有问题，，，emmmmm ，，，坑

小结

因为期中考试等等各种事，，，好久没弄acm的这些东西了，，大概有三周或则一个月了吧，，，

后果就是之前学的，记得东西又快忘记了，，，板子也不能自己的默写下来了QAQ，，

接下来这一个半月得好好的努力一把了，，，，，（逃

(end)