两道题都需要进行双向SPFA，比范例复杂，代码也较长，其中第二题应该可以用DFS或者BFS做，如果用DFS可能需要的剪枝较多。
ZOJ3088-Easter Holydays
//利用SPFA找出下降最长路径和上升最短路径，输出最大的比值和回路路径
//Time:0Ms Memory:328K
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std; #define MAX 1005
#define INF 0x3f3f3f3f struct Edge {
int u, w, next;
Edge(){}
Edge(int uu,int ww,int nn):u(uu),w(ww),next(nn){}
}eu[MAX], ed[MAX]; //up-down int n, m, k;
int hu[MAX], hd[MAX]; //邻接表头位置
int pu[MAX], pd[MAX]; //路径
int du[MAX], dd[MAX]; //最短路长
int tu[MAX], td[MAX]; //临时路径
bool v[MAX]; //上升最短路径
void spfa_u(int x)
{
memset(du, INF, sizeof(du));
memset(pu, -1, sizeof(pu));
memset(v, false, sizeof(v));
du[x] = 0;
queue<int> q;
q.push(x); pu[x] = x;
while (!q.empty()) {
int cur = q.front();
q.pop(); v[cur] = false;
for (int i = hu[cur]; i != -1; i = eu[i].next)
{
int u = eu[i].u, w = eu[i].w;
if (du[u] > du[cur] + w)
{
du[u] = du[cur] + w;
pu[u] = cur;
if (!v[u]) {
v[u] = true; q.push(u);
}
}
}
}
} //SPFA-下降最长路径
void spfa_d(int x)
{
memset(dd, -1, sizeof(dd));
memset(pd, -1, sizeof(pd));
memset(v, false, sizeof(v));
dd[x] = 0;
queue<int> q;
q.push(x); pd[x] = x;
while (!q.empty()) {
int cur = q.front();
q.pop(); v[cur] = false;
for (int i = hd[cur]; i != -1; i = ed[i].next)
{
int u = ed[i].u, w = ed[i].w;
if (dd[u] < dd[cur] + w)
{
dd[u] = dd[cur] + w;
pd[u] = cur;
if (!v[u]) {
v[u] = true; q.push(u);
}
}
}
}
} void path_u(int x)
{
if (tu[x] != x) path_u(tu[x]);
printf("%d ", x);
} void path_d(int x)
{
int i;
for (i = td[x]; i != td[i]; i = td[i])
printf("%d ", i);
printf("%d\n", i);
} int main()
{
int T;
scanf("%d", &T);
while (T--)
{
memset(hu, -1, sizeof(hu));
memset(hd, -1, sizeof(hd));
scanf("%d%d%d", &n, &m, &k);
int a, b, w;
for (int i = 0; i < m; i++)
{
scanf("%d%d%d", &a, &b, &w);
ed[i] = Edge(a, w, hd[b]); //反向建图
hd[b] = i;
}
for (int i = 0; i < k; i++)
{
scanf("%d%d%d", &a, &b, &w);
eu[i] = Edge(b, w, hu[a]); //正向建图
hu[a] = i;
} double rate = 0;
int tmp = -1;
for (int i = 1; i <= n; i++)
{
spfa_u(i); spfa_d(i);
for (int j = 1; j <= n; j++)
{
if (i == j || du[j] == INF) continue;
if (rate < 1.0 * dd[j] / du[j]) {
rate = 1.0 * dd[j] / du[j];
tmp = j;
memcpy(tu, pu, (n+1)*sizeof(int));
memcpy(td, pd, (n+1)*sizeof(int));
}
}
}
path_u(tmp); path_d(tmp);
printf("%.3f\n", rate);
}
return 0;
}
ZOJ3103-Cliff Climbing
//需要理清题意，比较复杂，建立双向邻接表，并须计算双向最短路
//第一次边表设大了MLE了...考虑最大边数 < n*18个，因此设为MAX*18
//Time:190Ms Memory:1152K
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std; #define MAXW 32
#define MAXH 62
#define MAX MAXW*MAXH
#define INF 0x3f3f3f3f
#define IN_RANGE(x,y) (x >= 0 && x < H && y >= 0 && y < W) struct Edge {
int u, w, next;
Edge() {}
Edge(int uu, int ww, int nn) :u(uu), w(ww), next(nn) {}
}e[2][MAX*18]; //0:左脚点 1::右脚点 int W, H, n;
int board[MAX];
int h[2][MAX], le[2];
int d[2][MAX]; //双向最短距离
bool v[MAX]; int mov0[9][2] = { { 0, 1 },{0, 2 },{0, 3 },{-1, 1 },{ -1, 2 },{ -2, 1 },{ 1, 1 },{ 1, 2 },{ 2, 1 } }; //左脚踩住，右脚移动位置
int mov1[9][2] = { { 0, -1},{0, -2},{0, -3},{-1, -1}, {-1, -2}, {-2, -1}, {1, -1}, {1, -2}, {2, -1} }; //右脚踩住，左脚移动位置 void spfa(int x)
{
memset(v, false, sizeof(v));
memset(d, INF, sizeof(d));
queue<int> q;
q.push(x); d[0][x] = d[1][x] = 0;
while (!q.empty()) {
int cur = q.front();
q.pop(); v[cur] = false;
for (int k = 0; k < 2; k++) //双向最短路
for (int i = h[k][cur]; i != -1; i = e[k][i].next)
{
int u = e[k][i].u;
int w = e[k][i].w;
if (d[!k][u] > d[k][cur] + w) //交叉影响
{
d[!k][u] = d[k][cur] + w;
if (!v[u]) {
v[u] = true; q.push(u);
}
} }
}
} int main()
{
while (scanf("%d%d", &W, &H), W && H)
{
char s[3];
n = W*H;
memset(h, -1, sizeof(h));
//一维序列表示各点
for (int i = 0; i < n; i++)
{
scanf("%s", s);
if (s[0] == 'S' || s[0] == 'T') board[i] = 0;
else if (s[0] == 'X') board[i] = INF;
else board[i] = s[0] - '0';
} //构建邻接表
le[0] = le[1] = 0;
for (int i = 0; i < n; i++)
{
if ((i < W && board[i] == 0) || board[i] == INF) continue;
for (int j = 0; j < 9; j++)
{
int x = i / W, y = i % W; //计算行与列
int x0 = x + mov0[j][0], y0 = y + mov0[j][1];
int x1 = x + mov1[j][0], y1 = y + mov1[j][1];
int n0 = x0*W + y0, n1 = x1*W + y1;
if (IN_RANGE(x0,y0) && board[n0] != INF) {
e[0][le[0]] = Edge(n0, board[n0], h[0][i]);
h[0][i] = le[0]++;
}
if (IN_RANGE(x1,y1) && board[n1] != INF) {
e[1][le[1]] = Edge(n1, board[n1], h[1][i]);
h[1][i] = le[1]++;
}
}
} int Min = INF;
for (int i = (H - 1) * W; i < n; i++) //枚举最后一行'S'进行SPFA
if (board[i] == 0)
{
spfa(i);
for (int j = 0; j < W; j++) //遍历第一行'T'的最短路长
if(board[j] == 0) Min = min(min(Min, d[0][j]), d[1][j]);
}
if (Min == INF) Min = -1;
printf("%d\n", Min);
}
return 0;
}