首页 > 代码库 > Codeforces 96D Volleyball spfa
Codeforces 96D Volleyball spfa
题目链接:点击打开链接
题意:
给定n个点m条边的无向图
起点、终点
下面m行表示边和边权
再下面n行表示每个点有一辆出租车,这辆出租车能开的最远距离和搭乘这辆车的费用
问到终点的最小费用
开始感觉复杂度太大不好下手,暴力出奇迹。。
Y一下即可得到 spfa套spfa
注意inf要足够大,__int64
#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> #include<math.h> #include<set> #include<queue> #include<map> #include<vector> using namespace std; #define N 1005 #define inf 10000000000000 #define ll __int64 struct Edge{ ll from, to, dis, nex; }edge[N<<1]; ll head[N],edgenum; void add(ll u,ll v,ll d){ Edge E = {u,v,d,head[u]}; edge[edgenum] = E; head[u] = edgenum++; } ll cost[N], far[N]; vector<ll>G[N]; ll dis[N]; bool vis[N], inq[N]; ll n, m, st, en; void dou(ll x){ if(vis[x])return; vis[x] = 1; for(ll i = 1; i <= n; i++)dis[i] = inf, inq[i] = 0; dis[x] = 0; queue<ll>q; q.push(x); while(!q.empty()){ ll u = q.front(); q.pop(); inq[u] = 0; for(ll i = head[u]; ~i; i = edge[i].nex){ ll v = edge[i].to; if(dis[u]+edge[i].dis<=far[x] && dis[v]>dis[u]+edge[i].dis){ dis[v] = edge[i].dis+dis[u]; if(!inq[v])inq[v] = 1, q.push(v); } } } for(ll i = 1; i <= n; i++)if(!vis[i] && dis[i]<=far[x])G[x].push_back(i); } ll ned[N]; bool hehe[N]; ll bfs(){ for(ll i = 1; i <= n; i++)ned[i] = inf, hehe[i] = 0; ned[st] = 0; queue<ll>q; q.push(st); hehe[en] = 1; while(!q.empty()){ ll u = q.front(); q.pop(); hehe[u] = 0; dou(u); for(ll i = 0; i < G[u].size(); i++){ ll v = G[u][i]; if(ned[v]>ned[u]+cost[u]){ ned[v] = ned[u]+cost[u]; if(!hehe[v])hehe[v]=1,q.push(v); } } } if(ned[en]==inf)return -1; return ned[en]; } void init(){ memset(vis, 0, sizeof vis); for(ll i = 1; i <= n; i++)G[i].clear(); memset(head,-1,sizeof head); edgenum = 0; } int main(){ ll i, j, u, v, d; while(cin>>n>>m){ init(); cin>>st>>en; while(m--){ cin>>u>>v>>d; add(u,v,d); add(v,u,d); } for(i=1;i<=n;i++)cin>>far[i]>>cost[i]; cout<<bfs()<<endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。