Week7：TT的美梦——最短路算法
题目描述
这一晚，TT 做了个美梦！
在梦中，TT 的愿望成真了，他成为了喵星的统领！喵星上有 N 个商业城市，编号 1 ～ N，其中 1 号城市是 TT 所在的城市，即首都。
喵星上共有 M 条有向道路供商业城市相互往来。但是随着喵星商业的日渐繁荣，有些道路变得非常拥挤。正在 TT 为之苦恼之时，他的魔法小猫咪提出了一个解决方案！TT 欣然接受并针对该方案颁布了一项新的政策。
具体政策如下：对每一个商业城市标记一个正整数，表示其繁荣程度，当每一只喵沿道路从一个商业城市走到另一个商业城市时，TT 都会收取它们（目的地繁荣程度 - 出发地繁荣程度）^ 3 的税。
TT 打算测试一下这项政策是否合理，因此他想知道从首都出发，走到其他城市至少要交多少的税，如果总金额小于 3 或者无法到达请悄咪咪地打出 ‘?’。
输入格式
第一行输入 T，表明共有 T 组数据。（1 <= T <= 50）
对于每一组数据，第一行输入 N，表示点的个数。（1 <= N <= 200）
第二行输入 N 个整数，表示 1 ～ N 点的权值 a[i]。（0 <= a[i] <= 20）
第三行输入 M，表示有向道路的条数。（0 <= M <= 100000）
接下来 M 行，每行有两个整数 A B，表示存在一条 A 到 B 的有向道路。
接下来给出一个整数 Q，表示询问个数。（0 <= Q <= 100000）
每一次询问给出一个 P，表示求 1 号点到 P 号点的最少税费。
输出格式
每个询问输出一行，如果不可达或税费小于 3 则输出 ‘?’。
输入样例
2
5
6 7 8 9 10
6
1 2
2 3
3 4
1 5
5 4
4 5
2
4
5
10
1 2 4 4 5 6 7 8 9 10
10
1 2
2 3
3 1
1 4
4 5
5 6
6 7
7 8
8 9
9 10
2
3 10
输出样例
Case 1:
3
4
Case 2:
?
?
题目分析
注意到这道题对图中的边的描述为：
对每一个商业城市标记一个正整数，表示其繁荣程度，当每一只喵沿道路从一个商业城市走到另一个商业城市时，TT 都会收取它们（目的地繁荣程度 - 出发地繁荣程度）^ 3 的税。
因此，我们可以发现，如果目的地的繁荣程度，不及出发地的繁荣程度，那么这条边就是一个负边——在最短路问题中一旦出现负边，这个图中就有可能出现负环，即负权回路。此时这个负权回路所能到达的所有的点的最短路都将会是无穷小，因为只需要在负环里绕圈圈就行了，这些点的结果也就对应了题目中对输出一个问号的要求的一部分。
处理带负权回路的图的最短路问题，迪杰斯特拉算法已经行不通了，我们需要使用贝尔曼福德算法——或者基于其的优化算法：SPFA，一个长得和bfs特别像的算法。
判断负环的方式就是判断某个点了：如果一个点进入队列的次数超过了所有点的总数，那么说明出现了负环，我们需要对着这个点进行深搜或者广搜，把这个点所能到达的所有点全部设置为无限小标记点，因为这个点既然能进入队列n次，说明顺着这个点肯定能到一个负权环路，并且这个负权环路还能回到这个点。
在SPFA算法的过程中对于某个点，判断一下是否是无限小标记点——如果是的话就跳过它——都无限小了还使用最短路算法干啥呢。此举以避免无限循环的发生。
这道题就是一个典型的带负环图的最短路的处理。
以下是代码：
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
const int INF = 0x3f3f3f3f;
const int MAXN = 205;using namespace std;struct Edge
{int v, w;Edge(int v,int w):v(v),w(w){}
};vector<Edge>road[MAXN];int dis[MAXN];
int visit[MAXN];
int ban[MAXN];
int enqueue_num[MAXN];
int city[MAXN];
int n, m, q;void Init()
{for (int i = 0; i < MAXN; i++) road[i].clear();memset(dis, INF, sizeof dis);memset(visit, 0, sizeof visit);memset(ban, 0, sizeof ban);memset(enqueue_num, 0, sizeof enqueue_num);memset(city, 0, sizeof city);
}void dfs(int x)
{ban[x] = 1;for (int i = 0; i < road[x].size(); i++){int v = road[x][i].v;if (ban[v] == 0){dfs(v);}}
}void spfa()
{queue<int>q;q.push(1);dis[1] = 0;visit[1] = 1;enqueue_num[1]++;while (!q.empty()){int u = q.front();q.pop();visit[u] = 0;for (int i = 0; i < road[u].size(); i++){int v = road[u][i].v;int w = road[u][i].w;if (ban[v]) continue;if (dis[v] > dis[u] + w){dis[v] = dis[u] + w;if (!visit[v]){visit[v] = 1;enqueue_num[v]++;if (enqueue_num[v] > n){dfs(v);}else{q.push(v);}}}}}
}int main()
{int T;cin >> T;int the_case = 1;while (T--){Init();cin >> n;for (int i = 1; i <= n; i++){cin >> city[i];}cin >> m;for (int i = 1, a, b; i <= m; i++){cin >> a >> b;int temp = city[b] - city[a];int w = temp * temp * temp;road[a].push_back(Edge(b, w));}spfa();cin >> q;cout << "Case " << the_case << ":" << endl;the_case++;for (int i = 0, p; i < q; i++){cin >> p;if (ban[p] || dis[p] < 3 || dis[p] == INF){cout << "?" << endl;}else{cout << dis[p] << endl;}}}
}
发布评论