版权声明：本文为博主原创文章，未经博主同意不得转载。 https://blog.csdn.net/qq574857122/article/details/33743269
题目链接：点击打开链接
题意：
给定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;
}