Learning4Fun ural 1930

/* 题意:给出一个图，有一个起点和终点，现在开车从起点驶向重点，路分为上坡和下坡。
 * 求一条从起点到终点的路径使得上下坡转换的次数最少。;
 * 解法：最短路，spfa。把一点拆成以上坡到达和下坡达到两个点。
 * dist[v][vt]=min(dist[v][vt],dist[u][ut]+(ut!=vt));
 */
#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
#include <cstdio>
#include <queue>
using namespace std;
#define vN 10001*2
#define vE 100001*2
#define inf 0x3fffffff
struct edge
{
    int v, next;
    int c;
} e[vE];
int head[vN], used[vN][2], en;
void addedge(int u, int v, int c)
{
    e[en].v = v;
    e[en].c = c;
    e[en].next = head[u];
    head[u] = en++;
}
int dist[vN][2];
int getv(int ut, int vt)
{
    if (ut == vt)
        return 0;
    return 1;
}
int spfa(int s, int t, int n)
{
    queue<int> q;
    memset(used, 0, sizeof(used));
    for (int i = 0; i <= n; i++)
    {
        dist[i][0] = inf;
        dist[i][1] = inf;
    }
    used[s][0] = 1;
    dist[s][0] = 0;
    dist[s][1] = 0;
    used[s][1] = 1;
    q.push(s);
    q.push(0);
    q.push(s);
    q.push(1);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        int ut = q.front();
        q.pop();
        for (int i = head[u]; i != -1; i = e[i].next)
        {
            int v = e[i].v;
            int vt = e[i].c;
            if (dist[v][vt] > dist[u][ut] + getv(ut, vt))
            {
                dist[v][vt] = dist[u][ut] + getv(ut, vt);
                if (!used[v][vt])
                {
                    q.push(v);
                    q.push(vt);
                    used[v][vt] = 1;
                }
            }

        }
    }
    return min(dist[t][0],dist[t][1]);
}
int main()
{
    //freopen("data.in", "r", stdin);
    memset(head, -1, sizeof(head));
    en = 0;
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int x, y;
        cin >> x >> y;
        addedge(x, y, 0);
        addedge(y, x, 1);
    }
    int s, t;
    cin >> s >> t;
    cout << spfa(s, t, n) << endl;

}