路线

思路与复杂度

BFS维护最短距离 dist 以及该距离下最多补给站数 best。首次到达时设距离并入队；遇到同一最短层的另一条入边时取 best 的最大值。BFS按层处理，因此父层的最优状态会在子层出队前完成。时间与空间 O(n+m)。

正确性与边界

分层松弛覆盖全部最短路线，不接受更长路线的补给数。

参考代码

#include<bits/stdc++.h>
using namespace std;int main(){ios::sync_with_stdio(0);cin.tie(0);int n,m,k;cin>>n>>m>>k;vector<int>s(n+1);for(int i=0,x;i<k;i++)cin>>x,s[x]=1;vector<vector<int>>g(n+1);while(m--){int u,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}vector<int>d(n+1,-1),b(n+1,-1);queue<int>q;d[1]=0;b[1]=s[1];q.push(1);while(q.size()){int u=q.front();q.pop();for(int v:g[u]){int nb=b[u]+s[v];if(d[v]<0)d[v]=d[u]+1,b[v]=nb,q.push(v);else if(d[v]==d[u]+1)b[v]=max(b[v],nb);}}if(d[n]<0)cout<<-1<<"\n";else cout<<d[n]<<" "<<b[n]<<"\n";}