算法

反过来搞一下最短路，即以t为源头，顺便记录一下到每个点有几条
假如 当前点到t的最短距离 不等于 后一个点到t的最短距离+1，则一定会更新
否则假如 当前点到t的路线数目 > 1，最大值+1，因为可能会更新，假如导航给的路线恰好是当前路线则不会

C++ 代码

#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PLL;
const int N = 2e5+10;
int h[N],ne[N],e[N],idx;
int d[N],cnt[N],p[N];
int n,m,k,s,t;
bool vis[N];
void add(int a,int b)
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}
void dij()
{
    memset(d,INF,sizeof(d));
    priority_queue<PLL,vector<PLL>,greater<PLL>> heap;
    d[t] = 0;
    heap.push({0,t});
    while(!heap.empty())
    {
        int t = heap.top().second;
        heap.pop();
        if(vis[t])
            continue;
        vis[t] = true;
        for(int i=h[t];~i;i=ne[i])
        {
            int j = e[i];
            if(!vis[j]&&d[j]>d[t]+1)
                d[j] = d[t]+1, cnt[j] = 1,heap.push({d[j],j});
            else if(d[j]==d[t]+1)
                cnt[j]++;
        }
    }
}
int main()
{
    memset(h,-1,sizeof(h));
    cin >>n>>m;
    for(int i=0;i<m;i++)
    {
        int u,v;
        cin >> u >> v;
        add(v,u);
    }
    cin >> k;
    for(int i=1;i<=k;i++)
        cin >> p[i];
    s = p[1] , t= p[k];
    dij();
    // for(int i=1;i<=n;i++)
    //     cout << d[i] << ' ' << cnt[i] <<endl;
    int mx = 0, mn = 0;
    for(int i=1;i<k;i++)
    {
        if(d[p[i]]!=d[p[i+1]]+1)
            mx++,mn++;
        else if(cnt[p[i]]>1)
                mx++;
    }
    cout << mn << ' ' << mx <<endl;
    return 0;
}