题目 题意: 给定n个点m条边的有向图,有两种边权,一种是现金,另一种是旅游金。可以在任意一点将现金转换成旅游金,但是之后走的路只能用旅游金,即第二种边权。每个点有自己的汇率,即1现金能换多少旅游金。有q次询问,每次询问将某个城市的汇率改变,改变是永久的,在线处理,求改变后1到n至少需要多少现金。保证有1到n的路径,可能存在重边或者自环。 思路: 思路倒也好想,求1到u的最短路,再求u到n的第二种边权的最短路,第二种边权的最短路建反边从n跑一下即可。之后注意要用multiset存下在所有点换现金的最小花费,否则发现过不了样例。因为可以多个点的最小花费相同,某个城市改变后不影响另一个最小花费的城市。 !wa了一个点,忘了对于每个中转点记判断一下是否不可达,有个点因为不可达二者相加爆ll了。 时间复杂度: O(mlogm+qlogn) 代码:
#include
using namespace std;
#define mem(a,x) memset(a,x,sizeof(a))
const int N = 1e5+10;
const int M = 2e5+10;
typedef long long ll;
#define int long long
typedef pair PII;
const int INF = 0x3f3f3f3f3f3f3f3f;
int n,m,k,T;int q;
int h[N],e[M],ne[M],w1[M],w2[M],idx = 0;
void add(int a,int b,int c,int d)
{
e[idx] = b,w1[idx] = c,w2[idx] = d,ne[idx] = h[a],h[a] = idx++;
}
int dist1[N];
int dist2[N];
bool vis[N];
int st,ed;
int a[N];
multiset sa;
struct node{
int x,y,z,z2;
}ee[M];
void Dij(int S,int dist[],int w[])
{
memset(dist,0x3f,sizeof(dist1));
// for(int i=1;i>y>>z>>z2;
ee[i] = {x,y,z,z2};
add(x,y,z,z2);
}
Dij(st,dist1,w1);
mem(h,-1); idx=0;
for(int i=0;ia[i];
Dij(ed,dist2,w2);
for(int u=1;u>u>>x;
if(dist1[u]==INF||dist2[u]==INF)
{
cout
关注
打赏
最近更新
- 深拷贝和浅拷贝的区别(重点)
- 【Vue】走进Vue框架世界
- 【云服务器】项目部署—搭建网站—vue电商后台管理系统
- 【React介绍】 一文带你深入React
- 【React】React组件实例的三大属性之state,props,refs(你学废了吗)
- 【脚手架VueCLI】从零开始,创建一个VUE项目
- 【React】深入理解React组件生命周期----图文详解(含代码)
- 【React】DOM的Diffing算法是什么?以及DOM中key的作用----经典面试题
- 【React】1_使用React脚手架创建项目步骤--------详解(含项目结构说明)
- 【React】2_如何使用react脚手架写一个简单的页面?