Travel 最短路

el/2024/5/21 22:14:56

链接:https://ac.nowcoder.com/acm/problem/14292
来源:牛客网

题目描述

精灵王国有N座美丽的城市,它们以一个环形排列在Bzeroth的大陆上。其中第i座城市到第i+1座城市花费的时间为d[i]。特别地,第N座城市到第1座城市花费的时间为d[N]。这些道路都是双向的。
另外,精灵们在数千年的时间里建造了M座传送门,第i座传送门连接了城市u[i]与城市v[i],并且需要花费w[i]的时间通过(可能有两座传送门连接了同一对城市,也有可能一座传送门连接了相同的两座城市)。这些传送门都是双向的。
小S是精灵王国交通部部长,她的职责是为精灵女王设计每年的巡查路线。每次陛下会从某一个城市到达另一个城市,沿路调查每个城市的治理情况,她需要找出一条用时最短的路线。

输入描述

第一行为2个整数N、M。
第二行为N个正整数d[i]。
接下来M行每行三个正整数u[i]、v[i]、w[i]。
第M+3行为一个正整数Q,表示需要设计路线的次数。
接下来Q行每行两个正整数x、y,表示一次从城市x到城市y的旅行。

输出描述

Q行每行一个正整数表示该次旅行的最短时间。

分析

一开始没仔细看题,直接暴力建图然后跑spfa,最后tle了。。。。

我们来分析一下这道题目,首先给了我们n个点,相邻的两个点以及首位的两个点之间连接了一条双向边,这样图中任意两个点都可以直接移动,通过的时间可以用前缀和进行计算

sum[y-1] - sum[x-1]

然后又新建了m条边m,并且m小于20,这就提醒我们,这么小的范围可以通过枚举新建的边的点,然后预处理一下这些点到所有点的距离,最后查表即可,x,y之间的距离为

d[i][x] + d[i][y]

两种移动方式取最小值即可

需要注意的是n的范围过大,如果d开二维数组可能会mle,所以可以选择将存好的点进行压缩处理

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <set>
#define debug(x) cout << #x << ':' << x << endl;using namespace std;
typedef long long ll;const int N = 525020,M = 3 * N;
const ll INF = 1e17;
int idx,h[N],ne[M],e[M];
ll w[M];
ll d[50][N];
bool st[N];
int n,m,q;
ll sum[N * 2];
ll a[N * 2];
set<int> S;void add(int x,int y,ll z){e[idx] = y,w[idx] = z,ne[idx] = h[x],h[x] = idx++;e[idx] = x,w[idx] = z,ne[idx] = h[y],h[y] = idx++;
}void spfa(int id,int s){for(int i = 1;i <= n;i++) d[id][i] = INF;d[id][s] = 0;queue<int>Q;Q.push(s);st[s] = true;while(!Q.empty()){int t = Q.front();st[t] = false;Q.pop();for(int i = h[t];~i;i = ne[i]){int j = e[i];if(d[id][j] > d[id][t] + w[i]){d[id][j] = d[id][t] + w[i];if(!st[j]){Q.push(j);st[j] = true;}}}}
}ll cal(int x,int y){return y >= x ? sum[y-1] - sum[x-1] : sum[n+y-1] - sum[x-1];
}int main(){memset(h,-1,sizeof h);scanf("%d%d",&n,&m);for(int i = 1;i <= n;i++) scanf("%lld",&a[i]);for(int i = n + 1;i <= n * 2;i++) a[i] = a[i - n];for(int i = 1;i <= 2 * n;i++) sum[i] = sum[i - 1] + a[i];for(int i = 1;i < n;i++) add(i,i + 1,a[i]);add(1,n,a[n]);while(m--){int x,y;ll z;scanf("%d%d%lld",&x,&y,&z);S.insert(x);S.insert(y);add(x,y,z);}int num = 0;for(auto p:S) spfa(num++,p);scanf("%d",&q);while(q--){int x,y;scanf("%d%d",&x,&y);ll ans = min(cal(x,y),cal(y,x));num = 0;for(auto p:S){ans = min(ans,d[num][x] + d[num][y]);num++;}printf("%lld\n",ans);}
}

http://www.ngui.cc/el/5239382.html

相关文章

飞行路线 |分层图初步学习

链接&#xff1a;https://ac.nowcoder.com/acm/problem/15073 来源&#xff1a;牛客网 题目描述 Alice和Bob现在要乘飞机旅行&#xff0c;他们选择了一家相对便宜的航空公司。该航空公司一共在n个城市设有业务&#xff0c;设这些城市分别标记为0到n-1&#xff0c;一共有m种航…

设计密码 —— 状态机

来源&#xff1a;acwing 题目描述 你现在需要设计一个密码 S&#xff0c;S 需要满足&#xff1a; S 的长度是 N&#xff1b; S 只包含小写英文字母&#xff1b; S 不包含子串 T&#xff1b; 例如&#xff1a;abc 和 abcde 是 abcde 的子串&#xff0c;abd 不是 abcde 的子串…

A. Remove Smallest

传送门 分析 这道题的意思大概是说有一串数字&#xff0c;你每次可以取出两个数字x&#xff0c;y&#xff0c;但要求是x和y相差不能超过1&#xff0c;然后你可以任意删去一个数字&#xff0c;这种操作可以进行无数次。 给你一个数组&#xff0c;然后让你判断能不能通过这种操…

迷宫2 ——单调队列解决bfs问题

链接&#xff1a;https://ac.nowcoder.com/acm/problem/15196 来源&#xff1a;牛客网 题目描述 这是一个关于二维格子状迷宫的题目。迷宫的大小为N*M&#xff0c;左上角格子座标为(1,1)、右上角格子座标为(1,M)、左下角格子座标为(N,1)、右下角格子座标为(N,M)。每一格都用-…

D. 505

传送门 分析 这个道题的题意是给你一个n * m的01矩阵&#xff0c;然后可以更改矩阵中的数字&#xff0c;比如把0改成1&#xff0c;或者把1改成0&#xff0c;要求最后矩阵中没有任何一个边长为偶数的子矩阵中含有偶数个1&#xff0c;如果不含偶数边长的子矩阵&#xff0c;则不…

Fluctuation Limit 构造

链接&#xff1a;http://acm.hdu.edu.cn/showproblem.php?pid6860. 来源&#xff1a;杭电多校第八场 题目描述 给你n个范围[li,ri]和一个整数x&#xff0c;要求构建一个长度为n的数组ai&#xff0c;要求保证ai > li && ai < ri,并且保证相邻两个x之间的差值的…

C. Boboniu and Bit Operations

传送门 分析 写的时候没注意到数据范围&#xff0c;一直在想dp的做法&#xff0c;后来才发现这个数据范围其实可以枚举暴力的 我们从0开始枚举答案&#xff0c;如果有一个答案满足对任意一个ai&#xff0c;均能找到一个bj&#xff0c;使得(a[i] & b[j]) | x) x&#xf…

D. Colored Rectangles

传送门 分析 个人感觉这道题比C简单&#xff08;一个DP选手最后的尊严&#xff09; 题目大意是说有三种不同的木棒&#xff0c;第一种木棒有a对&#xff0c;第二种b对&#xff0c;第三种c对&#xff0c;每次取两对不同的木棒组成一个矩形&#xff0c;问最后组成的若干个矩形…

D. Maximum Distributed Tree 思维+DFS

传送门 分析 这道题分析思路很简单——统计每条边的贡献&#xff0c;然后把权值和贡献进行排序&#xff0c;乘一下贪心即可 所以这道题的难点转换成了——我们如何去统计每条边的贡献值 我一开始的思路是用前向星存图&#xff0c;然后每条边进行离散化&#xff0c;最后跑一…

C. Multiples of Length 思维构造

传送门 题意 给你一个长度为n的数组&#xff0c;让你进行三次操作&#xff0c;选择一个l到r的区间&#xff0c;这段长度为r - l&#xff0c;然后对于这段区间内的每一个数字&#xff0c;你都可以加上或者减去这段长度的倍数&#xff0c;要求三次操作结束之后&#xff0c;数组…