题意：
2维平面上，要从起点到终点，中间有n个站台，站台之间有边。两点距离为欧几里得距离。每个边可以坐不同交通工具对应不同碳排放量。
求起点到终点距离不超过B且碳排放量最小的路径
思路：
二维dijkstra，定义 d [ i ] [ j ] d[i][j] d[i][j]为到了第 i i i个点距离为 j j j时的最低碳排放量。
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <cmath>
#include <queue>using namespace std;typedef long long ll;const int maxn = 1005;
const ll INF = 0x3f3f3f3f3f3f3f3f;ll d[maxn][105];
int vis[1005][105],cnt,n;
int head[maxn],nex[maxn * maxn],to[maxn * maxn],tot;
ll C[maxn],B,val1[maxn * maxn],val2[maxn * maxn];
vector<pair<int,int> >G[maxn];struct Node {int x,y;
}a[maxn];struct Heap {int x;ll w1,w2;bool operator < (const Heap&rhs) const {if(w2 == rhs.w2) return w1 > rhs.w1; //距离return w2 > rhs.w2; //碳排放量}
};void add(int x,int y,ll z1,ll z2) {to[++tot] = y;nex[tot] = head[x];val1[tot] = z1; //距离val2[tot] = z2; //co2head[x] = tot;
}void dijkstra() {priority_queue<Heap>Q;for(int i = 0;i <= n + 1;i++) {for(int j = 0;j <= B;j++) {d[i][j] = INF;}}d[0][0] = 0;Q.push({0,0,0});while(!Q.empty()) {Heap now = Q.top();Q.pop();int x = now.x,y = now.w1,z = now.w2;if(vis[x][y]) continue;vis[x][y] = 1;for(int j = head[x];j;j = nex[j]) {int v = to[j];int w1 = val1[j],w2 = val2[j];if(w1 + y > B) continue;if(d[v][w1 + y] > d[x][y] + w2) {d[v][w1 + y] = d[x][y] + w2;Q.push({v,w1 + y,d[v][w1 + y]});}}}
}ll dis(Node a,Node b) {double x1 = a.x,y1 = a.y;double x2 = b.x,y2 = b.y;return (ll)ceil(sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));
}int main() {Node sta,ed;scanf("%d%d%d%d",&sta.x,&sta.y,&ed.x,&ed.y);scanf("%lld%lld",&B,&C[0]);int T;scanf("%d",&T);for(int i = 1;i <= T;i++) scanf("%lld",&C[i]);scanf("%d",&n);a[0] = sta;a[n + 1] = ed;for(int i = 1;i <= n;i++) {int x,y,l;scanf("%d%d%d",&x,&y,&l);a[i].x = x;a[i].y = y;for(int j = 1;j <= l;j++) {scanf("%d%d",&x,&y);G[i].push_back({x,y});}}for(int i = 1;i <= n;i++) {for(int j = 0;j < G[i].size();j++) {int x = G[i][j].first,y = G[i][j].second;x++;double dist = dis(a[i],a[x]);add(i,x,dist,dist * C[y]);add(x,i,dist,dist * C[y]);}}for(int i = 1;i <= n;i++) {ll dist = dis(a[i],a[0]);add(i,0,dist,dist * C[0]);add(0,i,dist,dist * C[0]);dist = dis(a[i],a[n + 1]);add(i,n + 1,dist,dist * C[0]);add(n + 1,i,dist,dist * C[0]);}ll dist = dis(a[0],a[n + 1]);add(0,n + 1,dist,dist * C[0]);add(n + 1,0,dist,dist * C[0]);dijkstra();ll ans = INF;for(int i = 0;i <= B;i++) {ans = min(ans,d[n + 1][i]);}if(ans == INF) {printf("-1\n");}else printf("%lld\n",ans);return 0;
}