公司网站建设有什么好处,手机版景区网站,网奇e游通旅游网站建设系统如何修改上传到服务器,做分类信息网站模板勤劳的一更题目题解代码实现题目
C国有 n个大城市和 m 条道路#xff0c;每条道路连接这n个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这 m 条道路中有一部分为单向通行的道路#xff0c;一部分为双向通行的道路#xff0c;双向通行的道路在统计条数…
勤劳的一更题目题解代码实现题目
C国有 n个大城市和 m 条道路每条道路连接这n个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这 m 条道路中有一部分为单向通行的道路一部分为双向通行的道路双向通行的道路在统计条数时也计为 1条。
C国幅员辽阔各地的资源分布情况各不相同这就导致了同一种商品在不同城市的价格不一定相同。但是同一种商品在同一个城市的买入价和卖出价始终是相同的。
商人阿龙来到 C 国旅游。当他得知同一种商品在不同城市的价格可能会不同这一信息之后便决定在旅游的同时利用商品在不同城市中的差价赚回一点旅费。设 C 国 n 个城市的标号从 1~ n阿龙决定从1号城市出发并最终在 n 号城市结束自己的旅行。在旅游的过程中任何城市可以重复经过多次但不要求经过所有 n 个城市。阿龙通过这样的贸易方式赚取旅费他会选择一个经过的城市买入他最喜欢的商品――水晶球并在之后经过的另一个城市卖出这个水晶球用赚取的差价当做旅费。由于阿龙主要是来 C 国旅游他决定这个贸易只进行最多一次当然在赚不到差价的情况下他就无需进行贸易。
假设C国有C个大城市城市的编号和道路连接情况如下图单向箭头表示这条道路为单向通行双向箭头表示这条道路为双向通行。 假设 1~n号城市的水晶球价格分别为 4,3,5,6,1。
阿龙可以选择如下一条线路1-2-3-5并在2号城市以 3 的价格买入水晶球在 3号城市以 5的价格卖出水晶球赚取的旅费数为 2。
阿龙也可以选择如下一条线路 1-4-5-4-5并在第1次到达 5号城市时以1的价格买入水晶球在第 2次到达 4号城市时以 6的价格卖出水晶球赚取的旅费数为5。
现在给出n个城市的水晶球价格m 条道路的信息每条道路所连接的两个城市的编号以及该条道路的通行情况。请你告诉阿龙他最多能赚取多少旅费。
输入格式 第一行包含 2 个正整数 n和 m中间用一个空格隔开分别表示城市的数目和道路的数目。 第二行 n 个正整数每两个整数之间用一个空格隔开按标号顺序分别表示这 n 个城市的商品价格。 接下来 m 行每行有3个正整数x,y,z每两个整数之间用一个空格隔开。如果 z1表示这条道路是城市x到城市y之间的单向道路如果 z2表示这条道路为城市x和城市 y之间的双向道路。 输出格式 一 个整数表示最多能赚取的旅费。如果没有进行贸易则输出 0。
输入输出样例 输入 5 5 4 3 5 6 1 1 2 1 1 4 1 2 3 2 3 5 1 4 5 2 输出 5 说明/提示 【数据范围】 输入数据保证1 号城市可以到达n号城市。 对于 10%的数据1≤n≤6。 对于 30%的数据1≤n≤100。 对于 50%的数据不存在一条旅游路线可以从一个城市出发再回到这个城市。 对于 100%的数据1≤n≤1000001≤m≤5000001≤xy≤n1≤z≤21≤各城市 水晶球价格≤100。
题解
这种题做的时候 讲完题解后
首先可以知道1是肯定能到达n的那么就要在这多条路径中选一条最优的 Wmax−WminWmax-WminWmax−Wmin
那么考虑一个点x如果它是答案路径上的一点就必须满足1能走到x并且x还能走到n 1能走到x通常就是用bfsSPFA就找到了 对于x能否走到n的话就需要建反图从n倒着来找看n能走到哪些点 这样在正图中就代表着x能走到n
可以用SPFA正着倒着跑一边 正着从1开始跑跑到x就找这一路上的WminWminWmin 意味着从1到x这一条路上买商品的最低价格 倒着从n开始跑跑到x就找这一路上的WmaxWmaxWmax 意味着从x到n这一条路上卖商品的最高价格
最后我们再O(n)O(n)O(n)扫一遍数组找到这一个节点x更新答案就可以了
代码实现
#include queue
#include cstdio
#include vector
#include cstring
using namespace std;
#define MAXN 100005
vector int G[MAXN], GG[MAXN];
queue int q;
int n, m, result;
int w[MAXN];
int dis1[MAXN], dis2[MAXN];
bool vis[MAXN];void SPFA1 () {vis[1] 1;q.push ( 1 );while ( ! q.empty() ) {int t q.front();q.pop();vis[t] 0;for ( int i 0;i G[t].size();i ) {int v G[t][i];vis[v] 0;if (dis1[v] dis1[t] ) {dis1[v] dis1[t];if ( ! vis[v] ) {vis[v] 1;q.push ( v );}}if ( dis1[v] w[v] ) {dis1[v] w[v];if ( ! vis[v] ) {vis[v] 1;q.push ( v );}}}}
}void SPFA2 () {while ( ! q.empty() ) q.pop();q.push ( n );while ( ! q.empty() ) {int t q.front();q.pop();vis[t] 0;for ( int i 0;i GG[t].size();i ) {int v GG[t][i];if ( dis2[v] dis2[t] ) {dis2[v] dis2[t];if ( ! vis[v] ) {vis[v] 1;q.push ( v );}}if ( dis2[v] w[v] ) {dis2[v] w[v];if ( ! vis[v] ) {vis[v] 1;q.push ( v );}}}}
}int main() {scanf ( %d %d, n, m );for ( int i 1;i n;i )scanf ( %d, w[i] );for ( int i 1;i m;i ) {int x, y, z;scanf ( %d %d %d, x, y, z );if ( z 1 ) {G[x].push_back ( y );GG[y].push_back ( x );}else {G[x].push_back ( y );G[y].push_back ( x );GG[x].push_back ( y );GG[y].push_back ( x );}}memset ( dis1, 0x7f, sizeof ( dis1 ) );memset ( dis2, -1, sizeof ( dis2 ) );SPFA1 ();SPFA2 ();for ( int i 1;i n;i )if ( dis1[i] ! 0x7f7f7f7f dis2[i] ! -1 )result max ( result, dis2[i] - dis1[i] );printf ( %d, result ); return 0;
}
