本文主要是介绍2018 ccpc 女生赛 奢侈的旅行 (堆优化dijkstra),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
奢侈的旅行
Time Limit: 14000/7000 MS (Java/Others) Memory Limit: 512000/512000 K (Java/Others)Total Submission(s): 394 Accepted Submission(s): 78
这些城镇之间有 m
注意:本游戏中等级为正整数,但是积分可以是任意实数。
小Q位于 1
每组数据第一行包含两个整数 n,m(2≤n≤100000,1≤m≤200000)
接下来 m
从题意可以看出来这是一个最短路的问题,初始等级为1,所以总积分的计算可以用对数化简成log((1+a1)/1 * (1+a1+a2)/(1+a1)......)--->log(1+a1+a2+....an)。所以过程中计算总积分时先计算 1+cost ,最后再求log就可以。
spfa会超时。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
int n, m;
int head[200006], cnt;
struct Edge{int v, a, b, next;
}edge[200006];void add(int u, int v, int a, int b){edge[cnt].a = a;edge[cnt].b = b;edge[cnt].v = v;edge[cnt].next = head[u];head[u] = cnt++;
}struct node{int id;ll level;node(int id, ll level){this->id = id;this->level = level;}bool operator < (const node &x)const{return level > x.level;}
};
ll dis[100005];
int vis[100005];
int dijkstra(){memset(dis, INF, sizeof(dis));memset(vis, 0 ,sizeof(vis));priority_queue<node>q;q.push(node(1, 1));dis[1] = 1;while(!q.empty()){node temp = q.top();q.pop();int u = temp.id;if(u == n)for(int i = 1; i < 65; i++)if((1ll << i) > temp.level)return i - 1;if(vis[u])continue;vis[u] = 1;for(int i = head[u]; i != -1; i = edge[i].next){if((temp.level + edge[i].a) / temp.level >= (1ll << edge[i].b) && temp.level + edge[i].a < dis[edge[i].v]){dis[edge[i].v] = temp.level + edge[i].a;q.push(node(edge[i].v, dis[edge[i].v]));}}}return -1;
}int main(){int T, u, v, a, b;scanf("%d", &T);while(T--){cnt = 0;memset(head, -1, sizeof(head));scanf("%d%d", &n, &m);for(int i = 0; i < m; i++){scanf("%d%d%d%d", &u, &v, &a, &b);add(u, v, a, b);}printf("%d\n", dijkstra());}return 0;
}
这篇关于2018 ccpc 女生赛 奢侈的旅行 (堆优化dijkstra)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!