「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
1 7
3 6
6 10
Sample Output
2
样例说明
奶牛1和奶牛3参与值班即可．
样例说明
奶牛1和奶牛3参与值班即可．
题解
同遭遇战可以转换为最短路。。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<algorithm> #define pa pair<int,int> #define inf 1000000000 #define ll long long using namespace std; inline int read() { int x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } int n,T,cnt; bool vis[1000005]; int dis[1000005],last[1000005]; struct data{int to,next,v;}e[2000005]; void insert(int u,int v,int w) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w; } void dijkstra() { priority_queue<pa,vector<pa>,greater<pa> >q; for(int i=1;i<=T;i++)dis[i]=inf; dis[0]=0;q.push(make_pair(0,0)); while(!q.empty()) { int now=q.top().second;q.pop(); if(vis[now])continue;vis[now]=1; for(int i=last[now];i;i=e[i].next) if(dis[now]+e[i].v<dis[e[i].to]) { dis[e[i].to]=dis[now]+e[i].v; q.push(make_pair(dis[e[i].to],e[i].to)); } } } int main() { n=read();T=read(); for(int i=1;i<=T;i++) insert(i,i-1,0); for(int i=1;i<=n;i++) { int a=read(),b=read(); insert(a-1,b,1); } dijkstra(); if(dis[T]==inf)puts("-1"); else printf("%d\n",dis[T]); return 0; } |
计数器 9612868
OI 课件=>
OI 课件=>
为啥SPFA会TLE?
spfa上界是nm的
最短路做法太神了，Orzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz