奢侈的旅行

Time Limit: 14000/7000 MS (Java/Others) Memory Limit: 512000/512000 K (Java/Others)

Problem Description

高玩小Q不僅喜歡玩尋寶游戲，還喜歡一款升級養(yǎng)成類游戲。在這個游戲的世界地圖中一共有n個城鎮(zhèn)，編號依次為1到n。

這些城鎮(zhèn)之間有m條單向道路，第i 條單項(xiàng)道路包含四個參數(shù)ui,vi,ai,bi，表示一條從ui號城鎮(zhèn)出發(fā)，在vi號城鎮(zhèn)結(jié)束的單向道路，因?yàn)槭菃蜗虻缆?#xff0c;這不意味著小Q可以從vi沿著該道路走到ui。小Q的初始等級level為1，每當(dāng)試圖經(jīng)過一條道路時，需要支付cost=log2level+ailevel點(diǎn)積分，并且經(jīng)過該道路后，小Q的等級會提升ai級，到達(dá)level+ai級。但是每條道路都會在一定意義上歧視低消費(fèi)玩家，準(zhǔn)確地說，如果該次所需積分cost<bi，那么小Q不能經(jīng)過該次道路，也不能提升相應(yīng)的等級。

注意：本游戲中等級為正整數(shù)，但是積分可以是任意實(shí)數(shù)。

小Q位于1號城鎮(zhèn)，等級為1，現(xiàn)在為了做任務(wù)要到n號城鎮(zhèn)去。這將會是一次奢侈的旅行，請寫一個程序幫助小Q找到需要支付的總積分最少的一條路線，或判斷這是不可能的。

Input

第一行包含一個正整數(shù)T(1≤T≤30)，表示測試數(shù)據(jù)的組數(shù)。

每組數(shù)據(jù)第一行包含兩個整數(shù)n,m(2≤n≤100000,1≤m≤200000)，表示城鎮(zhèn)數(shù)和道路數(shù)。

接下來m行，每行四個整數(shù)ui,vi,ai,bi(1≤ui,vi≤n,ui≠vi,0≤ai≤109,0≤bi≤60)，分別表示每條單向道路。

Output

對于每組數(shù)據(jù)，輸出一行一個整數(shù)，即最少所需的總積分的整數(shù)部分，如：4.9999輸出4，1.0輸出1。若不存在合法路線請輸出?1。

Sample Input

1
3 3
1 2 3 2
2 3 1 6
1 3 5 0

Sample Output

2

Source

"字節(jié)跳動杯"2018中國大學(xué)生程序設(shè)計(jì)競賽-女生專場

Recommend

liuyiding

題解：根據(jù)(loga + logb) = logab這一個公式可以得到消耗總積分為log2(1+Sn)，盡量讓最后的等級小就可以了，這樣可以把等級看做邊的權(quán)值，求以b為限制的最短路。
優(yōu)先想到Dijstra，但數(shù)據(jù)量特別大，所以需要用堆優(yōu)化，基本是抄的模板。
(上面都是廢話，附上官方題解)

#include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> #include <vector> #include <queue>using namespace std; const int maxn = 1000050; const long long INF = 1e17+7;struct qnode {int v;long long c;qnode(int _v=0,long long _c=0):v(_v),c(_c){}bool operator <(const qnode &r)const{return c>r.c;} }; struct Edge {int to,w,MIN;Edge(int _to,int _w,int _MIN):to(_to),w(_w),MIN(_MIN){} };vector<Edge>E[maxn]; bool vis[maxn]; long long dis[maxn];void Dijstra(int n,int start) {memset(vis,false,sizeof(vis));for(int i=1;i<=n;i++)dis[i] = INF;priority_queue<qnode> que;while(!que.empty()) que.pop();dis[start] = 1;que.push(qnode(start,1));qnode tmp;while(!que.empty()){tmp = que.top();que.pop();int u = tmp.v;if(vis[u])continue;vis[u] = true;for(int i=0;i<E[u].size();i++){int v = E[u][i].to;int w = E[u][i].w;if(log2((dis[u]+w*1.0) / dis[u]*1.0)<E[u][i].MIN)continue;if(!vis[v]&&dis[v]>dis[u]+w){dis[v] = dis[u] + w;que.push(qnode(v,dis[v]));}}}//cout<<dis[n]<<endl;if(dis[n]==INF)printf("-1\n");elseprintf("%d\n",(int)log2(dis[n])); }int main() {int t,m,i,a,b,c,d,n;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);for(i=1;i<=n;i++)E[i].clear();for(i=0;i<m;i++){scanf("%d%d%d%d",&a,&b,&c,&d);E[a].push_back(Edge(b,c,d));}Dijstra(n,1);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/luoxiaoyi/p/9726829.html

總結(jié)

以上是生活随笔為你收集整理的HDU-6290_奢侈的旅行(Dijstra+堆优化)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。