bzoj1674: [Usaco2005]Part Acquisition　裸dijkstra

 1 #include <stdio.h>
 2 #include <queue>
 3 #include <string.h>
 4 #include <algorithm>
 5 #define inf 2000000000
 6 using namespace std;
 7 typedef pair<long long , int > pii;
 8 priority_queue <pii, vector<pii>, greater<pii > > q;
 9 struct node 
10 {
11     int u, v, w, next;
12 }a[100005];
13 int tot, n, m, rxa, rxc, rya, ryc;
14 int dis[100005];
15 int rp, T, first[100005];
16 int done[100005];
17 void addedge(int st, int end, int val)
18 {
19     a[++tot].u = st;a[tot].v = end;a[tot].w = val;
20     a[tot].next =first[st];first[st] = tot;
21 }
22 int dij()
23 {
24     for (int i = 1; i <= n; i++)dis[i] = inf;
25     q.push(make_pair(0, 1));
26     dis[1] = 0;
27     while (!q.empty())
28     {
29         int u = q.top().second;q.pop();
30         if(done[u])continue;
31         done[u] = 1;
32         for (int e = first[u]; e != -1; e = a[e].next)
33         {
34             int v = a[e].v;
35             if (dis[u] + a[e].w < dis[v])
36             {
37                 dis[v] = dis[u] + a[e].w;
38                 q.push(make_pair(dis[v], v));
39             }
40         }
41     }
42 }
43 int main()
44 {
45     scanf("%d %d", &m, &n);
46     int x, y;
47     memset(first, -1, sizeof(first));
48      for (int i = 1; i <= m; i++)
49      {
50         scanf("%d %d", &x, &y);
51         addedge(x, y, 1);
52      }
53      dij();
54      if(dis[n] == inf)printf("-1
");
55      else  printf("%d
", dis[n]+1);
56      return 0;
57 }
bzoj1674: [Usaco2005]Part Acquisition 裸dijkstra

bzoj1674: [Usaco2005]Part Acquisition　裸dijkstra
