D. Navigation System

题目链接：http://codeforces.com/contest/1321/problem/D

题目大意：

给你一张有向图，再给你一个路径，在路径的每一步上都维护最短路，如果不是按照最短路走就更新最短路，输出最小或最大更新次数（有最小或最大是因为最短路不唯一）。

想法：

反向连边跑dij，记录最短路以及最短路的条数

然而记录最短路条数需要重新正向连一次边

#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <math.h>
#include <cstdio>
#include <iomanip>
#include <time.h>
#include <bitset>
#include <cmath>
#include <sstream>
#include <iostream>

#define LL long long
#define INF 0x3f3f3f3f
#define ls nod<<1
#define rs (nod<<1)+1
#define pii pair<int,int>

const double eps = 1e-10;
const int maxn = 2e5 + 10;;
const LL mod = 1e9 + 7;

int sgn(double a){return a < -eps ? -1 : a < eps ? 0 : 1;}
using namespace std;

int head[maxn],head2[maxn];
int dist[maxn];
bool vis[maxn];
int cnt,cnt2;
int p[maxn],q[maxn];

struct Edge{
    int to,next;
}edge[maxn],e[maxn];

void init(){
    cnt = 0;
    cnt2 = 0;
    memset(head,-1, sizeof(head));
    memset(head2,-1, sizeof(head2));
    memset(vis,false, sizeof(vis));
    memset(dist,INF, sizeof(dist));
}

void add(int u,int v){
    edge[++cnt].to = v;
    edge[cnt].next = head[u];
    head[u] = cnt;
    int uu = v,vv = u;
    e[++cnt2].to = vv;
    e[cnt2].next = head2[uu];
    head2[uu] = cnt2;
}

void dijstra(int s)
{
    priority_queue<pii,vector<pii>,greater<pii> > q;
    dist[s] = 0;
    q.push({dist[s],s});
    while (!q.empty())
    {
        int now = q.top().second;
        q.pop();
        if (vis[now])
            continue;
        vis[now] = true;
        for (int i=head[now];i!=-1;i=edge[i].next)
        {
            int v = edge[i].to;
            if (dist[v]>dist[now]+1)
            {
                dist[v] = dist[now] + 1;
                q.push({dist[v],v});
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    init();
    int n,m;
    cin >> n >> m;
    for (int i = 1;i <= m;i++) {
        int u,v;
        cin >> u >> v;
        add(v,u);
    }
    int k;
    cin >> k;
    for (int i = 1;i <= k;i++)
        cin >> p[i];
    dijstra(p[k]);
    for (int i = 1;i <= n;i++) {
        for (int j = head2[i];~j;j = e[j].next) {
            int v = e[j].to;
            if (dist[v]+1 == dist[i])
                q[i]++;
        }
    }
    int maxx = 0,minn = 0;
    for (int i = 1;i < k;i++) {
        if (dist[p[i]] != dist[p[i+1]]+1)
            maxx++,minn++;
        else if (q[p[i]] > 1)
            maxx++;
    }
    cout << minn << " " << maxx << endl;
    return 0;
}