取消教育网站前置审批/北京seo关键词

问题描述

C国有 n 个大城市和 m 条道路，每条道路连接这 n 个城市中的某两个城市。

任意两个城市之间最多只有一条道路直接相连。

这 m 条道路中有一部分为单向通行的道路，一部分为双向通行的道路，双向通行的道路在统计条数时也计为1条。

C国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。

但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。

商人阿龙来到C国旅游。

当他得知“同一种商品在不同城市的价格可能会不同”这一信息之后，便决定在旅游的同时，利用商品在不同城市中的差价赚一点旅费。

设C国 n 个城市的标号从 1~n，阿龙决定从1号城市出发，并最终在 n 号城市结束自己的旅行。

在旅游的过程中，任何城市可以被重复经过多次，但不要求经过所有 n 个城市。

阿龙通过这样的贸易方式赚取旅费：他会选择一个经过的城市买入他最喜欢的商品——水晶球，并在之后经过的另一个城市卖出这个水晶球，用赚取的差价当做旅费。

因为阿龙主要是来C国旅游，他决定这个贸易只进行最多一次，当然，在赚不到差价的情况下他就无需进行贸易。

现在给出 n 个城市的水晶球价格，m 条道路的信息（每条道路所连接的两个城市的编号以及该条道路的通行情况）。

请你告诉阿龙，他最多能赚取多少旅费。

样例

输入样例：
5 5
4 3 5 6 1
1 2 1
1 4 1
2 3 2
3 5 1
4 5 2
输出样例：
5

思路：
用 dmin[x] 表示 1 - x的路径中值最小的点，dmax 代表 n - x 的路径中值最大的点，最后用dmax[x] - dmin[x] 求得最终结果，用两遍SPFA 分别更新最小值和最大值.

代码

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>using namespace std;const int N = 100010, M = 2000100;int e[M], ne[M], h[M], rh[M], len;
int a[N], dmin[N], dmax[N];
int n, m;
bool vis[N];void add(int *h, int a, int b)
{e[len] = b;ne[len] = h[a];h[a] = len++;
}void spfa()
{memset(dmin, 0x3f, sizeof dmin);queue<int> q;q.push(1);dmin[1] = a[1];vis[1] = true;while (q.size()){int x = q.front();q.pop();vis[x] = false;for (int i = h[x]; ~i; i = ne[i]){int y = e[i];if (dmin[y] > min(dmin[x], a[y])){dmin[y] = min(dmin[x], a[y]);if (!vis[y]){q.push(y);vis[y] = true;}}}}
}void spfa2()
{memset(dmax, -0x3f, sizeof dmax);memset(vis, false, sizeof vis);queue<int> q;q.push(n);dmin[n] = a[n];vis[n] = true;while (q.size()){int x = q.front();q.pop();vis[x] = false;for (int i = rh[x]; ~i; i = ne[i]){int y = e[i];if (dmax[y] < max(dmax[x], a[y])){dmax[y] = max(dmax[x], a[y]);if (!vis[y]){q.push(y);vis[y] = true;}}}}
}int main()
{memset(h, -1, sizeof h);memset(rh, -1, sizeof rh);scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++)scanf("%d", a + i);for (int i = 1; i <= m; i++){int a, b, c;scanf("%d%d%d", &a, &b, &c);add(h, a, b);add(rh, b, a);if (c == 2){add(h, b, a);add(rh, a, b);}}spfa();spfa2();int ans = -0x3f3f3f3f;for (int i = 1; i <= n; i++)ans = max(ans, dmax[i] - dmin[i]);printf("%d\n", ans);return 0;
}

代码二

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>using namespace std;const int N = 100010, M = 2000010;typedef pair<int, int> PII;
int e[M], w[M], ne[M], h[N], rh[N], len;
int n, m;
int cost[N];
int dmax[N], dmin[N];
bool vis[N];void add(int *h, int a, int b)
{e[len] = b;ne[len] = h[a];h[a] = len++;
}void spfa()
{memset(dmin, 0x3f, sizeof dmin);queue<int> q;q.push(1);dmin[1] = cost[1];vis[1] = true;while(q.size()){int x = q.front();vis[x] = false;q.pop();for(int i = h[x]; ~i; i = ne[i]){int y = e[i];if(dmin[y] > min(dmin[x], cost[y])){dmin[y] = min(dmin[x], cost[y]);if(!vis[y])q.push(y);}}}
}void dijkstra()
{priority_queue<PII> q;q.push({cost[n], n});dmax[n] = cost[n];while(q.size()){int x = q.top().second;q.pop();if(vis[x]) continue;vis[x] = true;for(int i = rh[x]; ~i; i = ne[i]){int y = e[i];if(dmax[y] < max(dmax[y], cost[y])){dmax[y] = max(dmax[y], cost[y]);q.push({dmax[y], y});}}}
}int main()
{scanf("%d%d", &n, &m);memset(h, -1, sizeof h);memset(rh, -1, sizeof rh);for(int i = 1; i <= n; i++)scanf("%d", cost + i);for(int i = 1; i <= m; i++){int a, b, c;cin >> a >> b >> c;add(h, a, b);add(rh, b, a);if(c == 2){add(h, b, a);add(rh, a, b);}}spfa();dijkstra();int ans = -0x3f3f3f3f;for(int i = 1; i <= n; i++){ans = max(dmax[i] - dmin[i], ans);}printf("%d", ans);return 0;
}