您当前的位置: 首页 > 

先求一个导

暂无认证

  • 3浏览

    0关注

    289博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

程序设计天梯赛L3-28 森森旅游(想到multiset就算成功)

先求一个导 发布时间:2022-04-21 10:56:39 ,浏览量:3

题目 题意: 给定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            
关注
打赏
1662037414
查看更多评论
0.0494s