Codeforces Round 918 (Div. 4)G题二维dijkstra

2024-01-13 00:20

本文主要是介绍Codeforces Round 918 (Div. 4)G题二维dijkstra,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

(读本文前需知dijkstra求最短路算法) 

目录

目标:

难点:

本题方法:

AC代码:


题目:Problem - G - Codeforces

目标:

本题是求1到n的最短路

难点:

本题的路径长度(即权值)是距离*自行车slowness

这就使得最短路很难求,比如第一个样例,就是绕到城市3选到slowness最小的自行车然后去终点最小

本题方法:

用ans[ i ]来表示城市 i 到终点n的最小长度   (很巧妙,看后面的变换去理解原因吧)

那么ans[1]就是答案

重点就是这个ans的变换了

从slowness最小的城市开始顺序dijkstra(可以求得该点到所有点的最短路)(多重dijkstra),这也包括到终点n的最短路

(为什么从slowness最小的城市开始呢,是贪心,我不好证明,,举个小反例:3经过4,ans[3]先于ans[4]算好了,但是3其实经过4可以有更短的(这需要4的slowness更小),此时ans[3]是错的

(slowness和城市下标捆绑排序(用个结构体,写个重载<就可以))

最短路求完进行这些操作:

1.ans[i] = dis[n];     //先把自己到终点的距离存了,然后看有没有更短的2.for(int j=1;j<=n;j++)    //遍历从1到n所有城市,看能否中转而有更短路径
{//也可能到不了城市j,或者城市j的slowness更大,没if(dis[j]!=0&&ans[j]!=0)    //必要比(更大所以还没有求最短路,所以ans[j]为0)ans[i] = min(ans[i],dis[j]+ans[j]);
}

AC代码:

(与上面的i,j不对应,dijkstra用了优先级队列做优化)

#define ll long long
int n, m; 
struct dis_node//放堆里面比长度,但是想知道端点
{ll dis;int next;bool operator < (const dis_node& a){return dis < a.dis;}dis_node(ll d,int n){dis = d; next = n;}
};
class cmp
{
public:bool operator()(dis_node a, dis_node b){return a.dis > b.dis;//}
};
void dijkstr(vector<set<int>>&arr, vector<vector<int>>&dis,int bike, int ori, vector<ll>&ans)
{priority_queue<dis_node, vector<dis_node>, cmp>heap;vector<ll>dij(n + 1);vector<int>barr(n+1);int cur = ori;while (1){for (auto next : arr[cur])//该次点所有可走的{//next就是下一个点(邻接表if (dij[next] == 0)dij[next] = dij[cur] + bike * dis[cur][next];//      + 此前的 + 这次的elsedij[next] = min(dij[next], dij[cur] + bike * dis[cur][next]);heap.push(dis_node(dij[next],next));}barr[cur] = 1;while (heap.size()){if (barr[heap.top().next] == 0)break;heap.pop();}if (heap.size() == 0)break;cur = heap.top().next;heap.pop();}//对ans做调整ans[ori] = dij[n];for (int i = 1; i <= n; i++){if (dij[i] != 0&& ans[i] != 0){ans[ori] = min(dij[i] + ans[i], ans[ori]);}}
}
struct s_i
{int slow, i;const bool operator<(const s_i& b){return slow < b.slow;}
};
void solve()
{cin >> n >> m;vector<set<int>>arr(n + 1);vector<ll>ans(n + 1);ans[1] = 0;vector<vector<int>>dis(n + 1, vector<int>(n + 1));vector<s_i>slowness(n+1);for (int i = 1; i <= m; i++){int u, v, w;cin >> u >> v >> w;arr[u].insert(v);arr[v].insert(u);//if (dis[u][v] == 0){dis[u][v] = w;dis[v][u] = w;}else{dis[u][v] = min(dis[u][v], w);dis[v][u] = min(dis[v][u], w);}}for (int i = 1; i <= n; i++){cin >> slowness[i].slow;slowness[i].i = i;}//sort(slowness.begin()+1, slowness.end());for(int i=1;i<=n;i++)dijkstr(arr, dis, slowness[i].slow, slowness[i].i,ans);cout << ans[1] << endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t; cin >> t;while (t--){solve();}return 0;
}

这篇关于Codeforces Round 918 (Div. 4)G题二维dijkstra的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/599663

相关文章

poj2576(二维背包)

题意:n个人分成两组,两组人数只差小于1 , 并且体重只差最小 对于人数要求恰好装满,对于体重要求尽量多,一开始没做出来,看了下解题,按照自己的感觉写,然后a了 状态转移方程:dp[i][j] = max(dp[i][j],dp[i-1][j-c[k]]+c[k]);其中i表示人数,j表示背包容量,k表示输入的体重的 代码如下: #include<iostream>#include<

hdu2159(二维背包)

这是我的第一道二维背包题,没想到自己一下子就A了,但是代码写的比较乱,下面的代码是我有重新修改的 状态转移:dp[i][j] = max(dp[i][j], dp[i-1][j-c[z]]+v[z]); 其中dp[i][j]表示,打了i个怪物,消耗j的耐力值,所得到的最大经验值 代码如下: #include<iostream>#include<algorithm>#include<

poj 1502 MPI Maelstrom(单源最短路dijkstra)

题目真是长得头疼,好多生词,给跪。 没啥好说的,英语大水逼。 借助字典尝试翻译了一下,水逼直译求不喷 Description: BIT他们的超级计算机最近交货了。(定语秀了一堆词汇那就省略吧再见) Valentine McKee的研究顾问Jack Swigert,要她来测试一下这个系统。 Valentine告诉Swigert:“因为阿波罗是一个分布式共享内存的机器,所以它的内存访问

uva 10801(乘电梯dijkstra)

题意: 给几个电梯,电梯0 ~ n-1分别可以到达很多层楼。 换乘电梯需要60s时间。 问从0层到target层最小的时间。 解析: 将进入第0层的电梯60s也算上,最后减。 坑点是如果target为0输出0。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algori

hdu 3790 (单源最短路dijkstra)

题意: 每条边都有长度d 和花费p,给你起点s 终点t,要求输出起点到终点的最短距离及其花费,如果最短距离有多条路线,则输出花费最少的。 解析: 考察对dijkstra的理解。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstrin

poj 3255 次短路(第k短路) A* + spfa 或 dijkstra

题意: 给一张无向图,求从1到n的次短路。 解析: A* + spfa 或者 dijkstra。 详解见上一题:http://blog.csdn.net/u013508213/article/details/46400189 本题,spfa中,stack超时,queue的效率最高,priority_queue次之。 代码: #include <iostream>#i

HDU 2159 二维完全背包

FATE 最近xhd正在玩一款叫做FATE的游戏,为了得到极品装备,xhd在不停的杀怪做任务。久而久之xhd开始对杀怪产生的厌恶感,但又不得不通过杀怪来升完这最后一级。现在的问题是,xhd升掉最后一级还需n的经验值,xhd还留有m的忍耐度,每杀一个怪xhd会得到相应的经验,并减掉相应的忍耐度。当忍耐度降到0或者0以下时,xhd就不会玩这游戏。xhd还说了他最多只杀s只怪。请问他能

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数,每次操作将其分成2^q份,对于每一份内部的数进行翻转(逆序),每次操作完后输出操作后新序列的逆序对数。 图一:  划分子问题。 图二: 分而治之,=>  合并 。 图三: 回溯:

Codeforces Round #261 (Div. 2)小记

A  XX注意最后输出满足条件,我也不知道为什么写的这么长。 #define X first#define Y secondvector<pair<int , int> > a ;int can(pair<int , int> c){return -1000 <= c.X && c.X <= 1000&& -1000 <= c.Y && c.Y <= 1000 ;}int m

Codeforces Beta Round #47 C凸包 (最终写法)

题意慢慢看。 typedef long long LL ;int cmp(double x){if(fabs(x) < 1e-8) return 0 ;return x > 0 ? 1 : -1 ;}struct point{double x , y ;point(){}point(double _x , double _y):x(_x) , y(_y){}point op