bzoj3389: [Usaco2004 Dec]Cleaning Shifts安排值班

Description

一天有T(1≤T≤10^6)个时段．约翰正打算安排他的N(1≤N≤25000)只奶牛来值班，打扫

打扫牛棚卫生．每只奶牛都有自己的空闲时间段[Si，Ei](1≤Si≤Ei≤T)，只能把空闲的奶牛安排出来值班．而且，每个时间段必需有奶牛在值班．那么，最少需要动用多少奶牛参与值班呢？如果没有办法安排出合理的方案，就输出-1.

Input

第1行：N，T．

第2到N+1行：Si，Ei．

Output

最少安排的奶牛数．

Sample Input

3 10
1 7
3 6
6 10

Sample Output

2

样例说明
奶牛1和奶牛3参与值班即可．

"其实这是经典的区间贪心题, 不过最短路可以做。
每个时间点建一个点, i 点向 i-1 点连一条权值 0 的有向边
对于区间 [l, r] , 那么 l − 1 向 r 连一条权值为 1 的有向边。从 0 时刻跑最
短路即可。"

——以上为某课件原文

然后放代码

 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 struct node 
 9 {
10     int u, v, w, next;
11 }a[5000005];
12 int tot, n, m, rxa, rxc, rya, ryc;
13 int dis[1000005];
14 int rp, T, first[1000005];
15 int done[1000005];
16 void addedge(int st, int end, int val)
17 {
18     a[++tot].u = st;a[tot].v = end;a[tot].w = val;
19     a[tot].next =first[st];first[st] = tot;
20 }
21 int dij()
22 {
23     priority_queue <pii, vector<pii>, greater<pii > > q;
24     for (int i = 0; i <= T; i++)dis[i] = inf;
25     q.push(make_pair(0, 0));
26     dis[0] = 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", &n, &T);
46     int x, y;
47     memset(first, -1, sizeof(first));
48     for(int i = 1; i <= T; i++)
49         addedge(i, i - 1, 0);
50      for (int i = 1; i <= n; i++)
51      {
52         scanf("%d %d", &x, &y);
53         addedge(x-1, y, 1);
54      }
55      dij();
56      if(dis[T] == inf)printf("-1
");
57      else  printf("%d
", dis[T]);
58      return 0;
59 }