Dijkstra、SPFA、Floyd、SPFA求负环
前言
非常非常经典的最短路问题，本文用了三种算法：Dijkstra、SPFA、Floyd
Dijkstra使用贪心思想，比较快，只可解决单源非负权值的最短路问题
SPFA是Bellman-Ford的队列优化，速度一般（有时候会超过Dijkstra），可以解决单源最短路问题
Floyd速度比较慢，可以解决点点最短路问题（听说如果不会Floyd可以外层套一层循环做Dijkstra也可解决 = =|| ）
鉴于SPFA实现比较简单，因此个人目前习惯用SPFA解决问题（希望出题人不要卡我T^T)
Til the Cows Come Home - POJ - 2387
题意
给定邻接链表求1到n的最短路
思路
模板题
Dijkstra做法：
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 2e5 + 15;
const int inf = 0x3f3f3f3f;
struct node{
int val, u;
node(int pv, int pu): val(pv), u(pu) {}
bool operator < (const node& b) const { return val > b.val; }
};
struct edge{
int v, val, next;
};
edge e[N];
int head[N];
int tot;
int d[N];
priority_queue<node> que;
inline void init(){
memset(d, 0x3f, sizeof(d));
memset(head, -1, sizeof(head));
tot = 0;
d[1] = 0;
}
inline void addEdge(int u, int v, int val){
e[tot].v = v;
e[tot].val = val;
e[tot].next = head[u];
head[u] = tot++;
}
void dijkstra(){
que.push(node(0, 1));
while(!que.empty()){
int val = que.top().val;
int u = que.top().u;
que.pop();
if(d[u] < val) continue;
for(int i = head[u]; ~i; i = e[i].next){
int v = e[i].v;
if(d[v] > d[u] + e[i].val){
d[v] = d[u] + e[i].val;
que.push(node(d[v], v));
}
}
}
}
int main(){
int n, m;
while(~scanf("%d%d", &n, &m)){
init();
while(n--){
int u, v, val;
scanf("%d%d%d", &u, &v, &val);
addEdge(u, v, val);
addEdge(v, u, val);
}
dijkstra();
printf("%d\n", d[m]);
}
}
SPFA做法：
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 2e5 + 15;
const int inf = 0x3f3f3f3f;
struct edge{
int v, val, next;
};
edge e[N];
int head[N];
int tot;
int d[N];
bool inque[N];
queue<int> que;
inline void init(){
memset(inque, false, sizeof(inque));
memset(d, 0x3f, sizeof(d));
memset(head, -1, sizeof(head));
tot = 0;
d[1] = 0;
}
inline void addEdge(int u, int v, int val){
e[tot].v = v;
e[tot].val = val;
e[tot].next = head[u];
head[u] = tot++;
}
void spfa(){
que.push(1);
inque[1] = true;
while(!que.empty()){
int u = que.front();
inque[u] = false;
que.pop();
for(int i = head[u]; ~i; i = e[i].next){
int v = e[i].v;
if(d[v] > d[u] + e[i].val){
d[v] = d[u] + e[i].val;
if(!inque[v]){
que.push(v);
inque[v] = true;
}
}
}
}
}
int main(){
int n, m;
while(~scanf("%d%d", &n, &m)){
init();
while(n--){
int u, v, val;
scanf("%d%d%d", &u, &v, &val);
addEdge(u, v, val);
addEdge(v, u, val);
}
spfa();
printf("%d\n", d[m]);
}
}
最短路径·二：Floyd算法 - HihoCoder - 1089
思路
教程 + 模板题
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 101;
int d[N][N];
inline void init(int n){
memset(d[0], 0x3f, sizeof(d));
for(int i = 1; i <= n; i++) d[i][i] = 0;
}
void floyd(int n){
for(int k = 1; k <= n; k++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
}
int main(){
int n, m;
while(~scanf("%d%d", &n, &m)){
init(n);
while(m--){
int u, v, val;
scanf("%d%d%d", &u, &v, &val);
d[u][v] = d[v][u] = min(val, d[u][v]);
}
floyd(n);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
printf("%d", d[i][j]);
if(j < n) putchar(' ');
}
puts("");
}
}
}
Frogger - POJ - 2253
题意
求源点到终点的路径中最大权值最小的那条路径中的权值最大值
思路
个人感觉不像单源最短路径，更像是最小生成树
首先算不同点的距离，填充邻接矩阵
然后参照最小生成树，将mincost定为当前维护的最大值，不断更新不同点的mincost，最后输出终点的mincost即可
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 505;
typedef long long ll;
const int inf = 0x3f3f3f3f;
struct node{
double cost;
int u;
node(double pc, int pu): cost(pc), u(pu) {}
bool operator < (const node& b) const { return cost > b.cost; }
};
double G[N][N];
double mincost[N];
int used[N];
int d[N][2];
priority_queue<node> que;
inline void init(){
for(int i = 0; i < N; i++) mincost[i] = inf;
memset(used, false, sizeof(used));
}
void prim(int n){
double ans = 0;
mincost[0] = 0;
que.push(node(0, 0));
while(!que.empty()){
int u = que.top().u;
double cost = que.top().cost;
que.pop();
if(used[u] || mincost[u] < cost) continue;
used[u] = true;
mincost[u] = cost;
ans = max(cost, ans);
for(int v = 0; v < n; v++){
if(u == v || G[u][v] == inf) continue;
if(!used[v] && mincost[v] > max(G[u][v], ans)){
mincost[v] = max(G[u][v], ans);
que.push(node(mincost[v], v));
}
}
}
}
int main(){
int n;
int caseno = 1;
while(scanf("%d", &n) && n){
init();
for(int i = 0; i < n; i++) scanf("%d%d", &d[i][0], &d[i][1]);
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(i == j){
G[i][j] = 0;
}else{
double dis = sqrt((d[i][0] - d[j][0]) * (d[i][0] - d[j][0]) + (d[i][1] - d[j][1]) * (d[i][1] - d[j][1]));
G[i][j] = G[j][i] = dis;
}
}
}
prim(n);
if(caseno > 1) puts("");
printf("Scenario #%d\n", caseno++);
printf("Frog Distance = %.3f\n", mincost[1]);
}
}
Silver Cow Party - POJ - 3268
题意
给定有向图，求任意点作为出发点，其到目标点，再从目标点回到对应的出发点的最小总路径中的最大值
思路
先从目标点跑最短路，可以计算出目标点到任意点的最短路径，再把图倒过来再跑一遍最短路，可以计算出任意点到目标点的最短路径，两者对应相加取最大就是答案了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1005 + 15;
typedef long long ll;
const int inf = 0x3f3f3f3f;
struct edge{ int v, val, next; };
int headt[N], head[N];
edge e[N*N], et[N*N];
int d[N], dt[N];
int tot;
queue<int> que;
inline void init(){
memset(head, -1, sizeof(head));
memset(headt, -1, sizeof(headt));
memset(d, 0x3f, sizeof(d));
memset(dt, 0x3f, sizeof(dt));
tot = 0;
}
inline void addEdge(int u, int v, int val){
e[tot].v = v;
e[tot].val = val;
e[tot].next = head[u];
head[u] = tot;
et[tot].v = u;
et[tot].val = val;
et[tot].next = headt[v];
headt[v] = tot++;
}
void spfa(int s, int n){
que.push(s);
d[s] = 0;
while(!que.empty()){
int u = que.front();
que.pop();
for(int i = head[u]; ~i; i = e[i].next){
int v = e[i].v;
if(d[v] > d[u] + e[i].val){
d[v] = d[u] + e[i].val;
que.push(v);
}
}
}
que.push(s);
dt[s] = 0;
while(!que.empty()){
int u = que.front();
que.pop();
for(int i = headt[u]; ~i; i = et[i].next){
int v = et[i].v;
if(dt[v] > dt[u] + et[i].val){
dt[v] = dt[u] + et[i].val;
que.push(v);
}
}
}
}
int main(){
int n, m, s;
while(~scanf("%d%d%d", &n, &m, &s)){
init();
while(m--){
int u, v, val;
scanf("%d%d%d", &u, &v, &val);
addEdge(u, v, val);
}
spfa(s, n);
int ans = 0;
for(int i = 1; i <= n; i++){
ans = max(ans, d[i] + dt[i]);
}
printf("%d\n", ans);
}
}
Currency Exchange - POJ - 1860
题意
有n种货币，m种兑换方式，现在Nick持有第s种货币，其金额为w，在m种兑换方式中，每一种的形式都是将a货币兑换成b货币，需要c1元手续费，其比率为r1;将b货币兑换为a货币，需要c2元手续费，其比率为r2。现在问Nick能否通过不断地兑换，最终重新兑换回原有货币，其金额增加
思路
实际上就是找一个权值为正的环，所以用到SPFA判负环的思想
注意这里边的权值应为 (a货币 - 手续费)*(1 + 比率)
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <map>
using namespace std;
const int N = 1005;
const int inf = 0x3f3f3f3f;
struct edge{
int v, next;
double commision, rate;
};
edge e[N << 1];
int head[N];
int tot;
double d[N];
bool inque[N];
queue<int> que;
inline void init(){
memset(head, -1, sizeof(head));
memset(inque, false, sizeof(inque));
memset(d, 0, sizeof(d));
tot = 0;
}
inline void addEdge(int u, int v, double commision, double rate){
e[tot].v = v;
e[tot].rate = rate;
e[tot].commision = commision;
e[tot].next = head[u];
head[u] = tot++;
}
bool spfa(int s, double base){
d[s] = base;
que.push(s);
while(!que.empty()){
int u = que.front();
que.pop();
inque[u] = false;
for(int i = head[u]; ~i; i = e[i].next){
int v = e[i].v;
if(d[v] < (d[u] - e[i].commision) * e[i].rate){
d[v] = (d[u] - e[i].commision) * e[i].rate;
if(!inque[v]){
que.push(v);
inque[v] = true;
}
}
if(d[s] > base) return true;
}
}
return false;
}
int main(){
int n, m, s;
double base;
while(~scanf("%d%d%d%lf", &n, &m, &s, &base)){
init();
while(m--){
int u, v;
double commision1, rate1, commision2, rate2;
scanf("%d%d%lf%lf%lf%lf", &u, &v, &rate1, &commision1, &rate2, &commision2);
addEdge(u, v, commision1, rate1);
addEdge(v, u, commision2, rate2);
}
puts(spfa(s, base) ? "YES" : "NO");
}
}
Subway - POJ - 2502
题意
你现在要从家到学校去，你的步行速度是10km/h，地铁的速度为40km/h，现在给定你家的坐标和学校的坐标，与地铁线路，及其每条线路对应站点的坐标（上述坐标均以m为单位），现在问选择怎样的方案能够最快时间内到达学校，求这个最小时间（以min为单位）
思路
这题就是建模挺烦，首先单位换算，然后边的权值就可以以min为单位了
然后构图，点点之间加一条步行所花时间的边，同线路相邻的地铁站点间加一条坐地铁所花时间的边
最后跑最短路，得到答案
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 205;
const double inf = 1e8;
struct node{
int id;
double x, y;
node(int pid, double px, double py): id(pid), x(px), y(py) {}
};
struct edge{
double val;
int v, next;
};
edge e[N*N << 2];
int tot;
int head[N];
double d[N];
queue<int> que;
bool inque[N];
vector<node> vec[N];
vector<node> nd;
inline void init(){
for(int i = 0; i < N; i++) vec[i].clear();
nd.clear();
for(int i = 0; i < N; i++) d[i] = inf;
memset(head, -1, sizeof(head));
memset(inque, false, sizeof(inque));
tot = 0;
}
inline void addEdge(int u, int v, double val){
e[tot].v = v;
e[tot].val = val;
e[tot].next = head[u];
head[u] = tot++;
}
inline double getDis(double x1, double y1, double x2, double y2){
return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
void spfa(){
d[1] = 0;
inque[1] = true;
que.push(1);
while(!que.empty()){
int u = que.front();
que.pop();
inque[u] = false;
for(int i = head[u]; ~i; i = e[i].next){
int v = e[i].v;
if(d[v] > d[u] + e[i].val){
d[v] = d[u] + e[i].val;
if(!inque[v]){
inque[v] = true;
que.push(v);
}
}
}
}
}
int main(){
ios::sync_with_stdio(false);
double sx, sy, tx, ty;
while(cin >> sx >> sy >> tx >> ty){
init();
nd.push_back(node(1, sx, sy));
nd.push_back(node(2, tx, ty));
int line = 1;
int id = 3;
double x, y;
while(cin >> x >> y){
if(x != -1 && y != -1){
node tmp(id, x, y);
vec[line].push_back(tmp);
nd.push_back(tmp);
id++;
}else{
line++;
}
}
line--;
for(int i = 0; i < nd.size(); i++){
for(int j = i + 1; j < nd.size(); j++){
double dis = getDis(nd[i].x, nd[i].y, nd[j].x, nd[j].y);
addEdge(nd[i].id, nd[j].id, dis*60/(1e4));
addEdge(nd[j].id, nd[i].id, dis*60/(1e4));
}
}
for(int i = 1; i <= line; i++){
for(int j = 0; j < vec[i].size() - 1; j++){
double dis = getDis(vec[i][j].x, vec[i][j].y, vec[i][j + 1].x, vec[i][j + 1].y);
addEdge(vec[i][j].id, vec[i][j + 1].id, dis*15/(1e4));
addEdge(vec[i][j + 1].id, vec[i][j].id, dis*15/(1e4));
}
}
spfa();
cout << (int)(d[2] + 0.5) << endl;
}
}
昂贵的聘礼 - POJ - 1062
思路
冬训的时候的题目，现在回去看自己当时的代码，实在是惨不忍睹……所以花了时间改了代码
将原物品的价格看作点的权值，而如果有替代品后的优惠价格看作边的权值，这样子从源点跑最短路，就能刚好符合题意。
跑的过程中注意维护等级限制的区间，最后，到每个点的最短路+该点的权值 中的最小值就是答案了
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef long long ll;
const int N = 105;
const int inf = 0x3f3f3f3f;
struct node{
int u, val, upper, lower;
node(int pu, int pv, int pupper, int plower): u(pu), val(pv), upper(pupper), lower(plower) {}
bool operator < (const node& b) const { return val > b.val; }
};
struct edge { int v, val, next; };
int head[N];
edge e[N*N];
bool used[N];
int val[N];
int lv[N];
int d[N];
int tot;
priority_queue<node> que;
inline void init(){
memset(head, -1, sizeof(head));
memset(used, false, sizeof(used));
memset(d, 0x3f, sizeof(d));
d[1] = 0;
tot = 0;
}
void addEdge(int u, int v, int val){
e[tot].val = val;
e[tot].v = v;
e[tot].next = head[u];
head[u] = tot++;
}
void dijkstra(int u, int n, int lv_lim){
que.push(node(1, 0, lv[1] + lv_lim, lv[1] - lv_lim));
while(!que.empty()){
int u = que.top().u;
int val = que.top().val;
int upper = que.top().upper;
int lower = que.top().lower;
que.pop();
if(used[u] || val > d[u]) continue;
used[u] = true;
for(int i = head[u]; ~i; i = e[i].next){
int v = e[i].v;
if(!used[v] && lv[v] <= upper && lv[v] >= lower && d[v] > d[u] + e[i].val){
d[v] = d[u] + e[i].val;
int vupper = min(upper, lv[v] + lv_lim);
int vlower = max(lower, lv[v] - lv_lim);
que.push(node(v, d[v], vupper, vlower));
}
}
}
}
int main(){
int lv_lim, n;
while(~scanf("%d%d", &lv_lim, &n)){
init();
for(int u = 1; u <= n; u++){
int m;
scanf("%d%d%d", &val[u], &lv[u], &m);
while(m--){
int v, val;
scanf("%d%d", &v, &val);
addEdge(u, v, val);
}
}
dijkstra(1, n, lv_lim);
int ans = inf;
for(int u = 1; u <= n; u++){
ans = min(ans, val[u] + d[u]);
}
printf("%d\n", ans);
}
return 0;
}
