传送门 这道题题意就不说了，主要是有一个二维数组进行 v i s vis vis 标记，因为该段路程的长度上限 B B B 仅仅只是100，所以完全可以用数组标记
d i j k s t r a dijkstra dijkstra 的优先队列排序是先二氧化碳排放量，再进行长度， v i s [ p o i n t ] [ l e n g t h ] vis[point][length] vis[point][length] 表示在点 v v v 长度为 l e n len len 的已经访问过了，直接跳过这个情况，剩下的就按部就班的 d i j k s t r a dijkstra dijkstra
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll> pll; template <typename T> inline void rd(T& x) { int tmp = 1; char c = getchar(); x = 0; while (c > '9' || c < '0') { if (c == '-')tmp = -1; c = getchar(); } while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } x *= tmp; } const int inf = 0x3f3f3f3f; const int mod = 998244353; const int N = 1e3 + 10; const int M=1e7+10; const double eps=1e-8; struct Point{ double x,y; void input(){ scanf("%lf %lf",&x,&y); } }st,ed,sta[N]; int B; int C[105]; int head[N],cnt; struct edge{ int next,to; int w0; }e[M]; void add(int u,int v,int w){ e[cnt].to=v; e[cnt].next=head[u]; e[cnt].w0=w; head[u]=cnt++; } struct node{ int cost,len; int u,fa; node(int u,int cost,int len,int fa):u(u),cost(cost),len(len),fa(fa){ } bool friend operator<(const node &a,const node &b){ if(a.cost==b.cost) return a.len>b.len; return a.cost>b.cost; } }; int n; bool vis[N][105]; int dis[N][N]; int dijkstra(){ priority_queue<node>que; que.push(node(n,0,0,-1)); memset(vis,false,sizeof vis); int ans=inf,len,cost,v; while(!que.empty()){ node vn=que.top();que.pop(); if(vn.u==n+1){ return vn.cost; } if(vis[vn.u][vn.len]) continue; vis[vn.u][vn.len]=true; for(int i=head[vn.u];~i;i=e[i].next){ v=e[i].to; if(v==vn.fa) continue; len=dis[vn.u][v]; if(vn.len+len>B||vis[v][vn.len+len]) continue; cost=len*e[i].w0; que.push(node(v,vn.cost+cost,vn.len+len,v)); } } return -1; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); memset(head,-1,sizeof head);cnt=0; st.input();ed.input(); rd(B); rd(C[0]);int T;rd(T); for(int i=1;i<=T;++i) rd(C[i]); rd(n); for(int i=0;i<n;++i){ sta[i].input(); int t;rd(t); while(t--){ int j,mj;rd(j),rd(mj); add(i,j,C[mj]); add(j,i,C[mj]); } } sta[n]=st;sta[n+1]=ed; for(int i=0;i<n;++i) add(n,i,C[0]); for(int i=0;i<=n;++i) add(i,n+1,C[0]); for(int i=0;i<=n+1;++i){ for(int j=i+1;j<=n+1;++j){ dis[i][j]=dis[j][i]=ceil(hypot(sta[i].x-sta[j].x,sta[i].y-sta[j].y)); } } printf("%d\n",dijkstra()); return 0; }