1930. Ivan's Car（ｓｐｆａ）

１９３０

简单二维　标记一下是上坡还是下坡

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 #include<queue>

 using namespace std;

 #define N 10010

 #define INF 0xfffffff

 int dis[N][],vis[N];

 int n;

 struct node

 {

     int u,v,next,d;

 }ed[N*];

 int t,head[N];

 void init()

 {

     t = ;

     memset(head,-,sizeof(head));

 }

 void add(int u,int v,int d)

 {

     ed[t].u = u;

     ed[t].v = v;

     ed[t].d = d;

     ed[t].next = head[u];

     head[u] = t++;

 }

 int spfa(int s,int e)

 {

     int i;

     for(i = ; i <= n ;i++)

     {

         dis[i][] = INF;

         dis[i][] = INF;

     }

     dis[s][] = ;

     dis[s][] = ;

     queue<int>q;

     q.push(s);

     vis[s] = ;

     while(!q.empty())

     {

         int u = q.front();

         q.pop();

         for(i = head[u] ; i != - ; i = ed[i].next)

         {

             int v = ed[i].v;

             int d = ed[i].d;

             if(d)

             dis[v][] = min(min(dis[u][],dis[u][]+),dis[v][]);

             else

             dis[v][] = min(min(dis[u][],dis[u][]+),dis[v][]);

             if(!vis[v])

             {

                 vis[v] =  ;

                 q.push(v);

             }

         }

     }

     return min(dis[e][],dis[e][]);

 }

 int main()

 {

     int i,u,v,m;

     init();

     scanf("%d%d",&n,&m);

     for(i = ; i <= m ;i++)

     {

         scanf("%d%d",&u,&v);

         add(u,v,);

         add(v,u,);

     }

     int s,e;

     scanf("%d%d",&s,&e);

     printf("%d\n",spfa(s,e));

     return ;

 }