wordpress模块化建站,客户管理系统admin,建设网站 费用吗,怎样才能做一个优质的外贸网站Codeforces Round 918 (Div. 4)
G. Bicycles G. Bicycles
题意#xff1a;
斯拉夫的所有朋友都打算骑自行车从他们住的地方去参加一个聚会。除了斯拉维奇#xff0c;他们都有一辆自行车。他们可以经过 n n n 个城市。他们都住在城市 1 1 1 #xff0c;想去参加位于城市…Codeforces Round 918 (Div. 4)
G. Bicycles G. Bicycles
题意
斯拉夫的所有朋友都打算骑自行车从他们住的地方去参加一个聚会。除了斯拉维奇他们都有一辆自行车。他们可以经过 n n n 个城市。他们都住在城市 1 1 1 想去参加位于城市 n n n 的聚会。城市地图可以看作一个无向图有 n n n 个节点和 m m m 条边。边 i i i 连接城市 u i u_i ui 和 v i v_i vi 长度为 w i w_i wi 。
斯拉夫没有自行车但他有的是钱。每个城市都有一辆自行车出售。在 i i i 这个城市中自行车的速度系数为 s i s_{i} si 。一旦斯拉维奇买了一辆自行车他就可以在任何时候用它从他现在所在的城市前往任何邻近的城市只需花费 w i ⋅ s j w_i \cdot s_j wi⋅sj 时间因为他是在用自己拥有的自行车 j j j 穿越边缘 i i i 。
斯拉维奇想买多少辆自行车都可以因为钱对他来说不是问题。由于斯拉维奇不喜欢骑自行车旅行他希望在最短的时间内从他的住处到达聚会地点。由于他的信息技能很生疏他需要你的帮助。
斯拉夫从城市 1 1 1 到城市 n n n 所需的最短时间是多少斯拉夫没有自行车就无法旅行。保证斯拉夫可以从城市 1 1 1 到达其他任何城市。
思路
很好的一个变型dijkstra。先放一下dijkstra的证明过程 写的很抽象但是证明思路很明显如果我们从堆里所有状态中选出走过的路长度最少的状态如果这个状态所在位置之前还没有被访问过那么现在这个状态走过的路长度就是最短的我的意思是之后到达这个位置的最短路径就再也不可能被刷新了。证明是显然的现在所有状态走过的路的长度都大于这个状态我们继续走下去只会使得走的路变长无论从什么状态来推之后到达的时候长度一定不可能小于现在的长度了。
一眼看下来感觉应该是个最短路问题用dijkstra但是由于我们可以先去一个其他城市买到一个更快的车子然后用这个车子到达终点结果可能更优所以直接跑dij是不对的。
考虑到我们到一个城市的时候只看原点到它的距离而不看手上的自行车是有可能不优的。但是如果多存储一维自行车的慢速因子来描述我们到这个城市的距离就是最优的了。具体来说原本的 d i s dis dis 数组设为 d i s [ u ] [ b i k e ] dis[u][bike] dis[u][bike] 表示到达城市 u u u手上最快的自行车为 b i k e bike bike 的最短距离这样 u , b i k e u,bike u,bike 确定时距离一定是越小越好的而不会对后面产生影响。
做法就出来了。 d i s dis dis 数组多描述一维自行车的慢速因子优先队列存储的状态多存储一个手上最快的自行车的信息就可以了。这里因为我们自行车一定是会越来越快的而我们经过的点最长是先到一个城市买最快的自行车再回来走到终点因此时间复杂度差不多是 O ( 2 n m l o g n ) O(2nmlogn) O(2nmlogn) 的。
到达某个点带有某个自行车的最近距离这里其实很像动态规划的思想。不如说dijkstra本身就很有动态规划的味道。比较类似的有这里的E题
code
#include iostream
#include cstdio
#include cstring
#include queue
using namespace std;
typedef long long ll;
const int maxn1005;
const ll inf1e9;int T,n,m;int head[maxn],counter;
struct EDGE{int v,w,nxt;
}e[maxn1];
void adde(int u,int v,int w){e[counter].vv;e[counter].ww;e[counter].nxthead[u];head[u]counter;
}
void init(){cinnm;memset(head,0,sizeof(head));counter0;for(int i1,u,v,w;im;i){cinuvw;adde(u,v,w);adde(v,u,w);}
}struct node{ll cost;int bike,u;bool operator(const node x)const{return (costx.cost)?bikex.bike:costx.cost;}
};
int s[maxn];
ll d[maxn][maxn];ll dijkstra(){memset(d,0x3f,sizeof(d));priority_queuenode h;d[1][s[1]]0;h.push(node{1,s[1],1});while(!h.empty()){int uh.top().u,bikeh.top().bike;h.pop();if(un)return d[u][bike];if(bikes[u]){d[u][s[u]]min(d[u][s[u]],d[u][bike]);bikes[u];}for(int ihead[u],v,w;i;ie[i].nxt){ve[i].v;we[i].w;if(d[v][bike]d[u][bike]1ll*bike*w){d[v][bike]d[u][bike]1ll*bike*w;h.push(node{d[v][bike],bike,v});}}}return inf;
}int main(){cinT;while(T--){init();for(int i1;in;i)cins[i];coutdijkstra()endl;}return 0;
}
