题目链接：http://poj.org/problem?id=1716
大致题意：
给出数轴上的n个区间，每个区间都是连续的int区间。
现在要在数轴上任意取一堆元素，构成一个元素集合V
要求每个区间和元素集合V的交集至少有两个不同的元素
求集合V最小的元素个数。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int maxn = 30005;
const int N = 10005;
int dis[N], head[N], time[N], cnt;
bool vis[N];
struct Edge
{int fro, to, w, next;
}edge[maxn];
void add_edge(int u, int v, int w)
{edge[cnt].fro = u;edge[cnt].to = v;edge[cnt].w = w;edge[cnt].next = head[u];head[u] = cnt++;
}
int spfa(int s, int n)
{int kkk = 0;memset(dis, -1, sizeof(dis));memset(time, 0, sizeof(time));memset(vis, false , sizeof(vis));dis[s] = 0;vis[s] = true;time[s]++;queue<int> q;q.push(s);while(!q.empty()){int tem = q.front();vis[tem] = false;q.pop();for(int i = head[tem]; i != -1; i = edge[i].next){int to = edge[i].to;if(dis[to] < dis[tem] + edge[i].w){dis[to] = dis[tem] + edge[i].w;if(!vis[to]){vis[to] = true;q.push(to);time[to]++;}}}}return dis[n - 1];
}
int main()
{int n, u, v, w, ma;while(cin >> n){cnt = ma = 0;memset(head, -1, sizeof(head));for(int i = 1; i <= n; i++){scanf("%d%d", &u, &v);if(v + 1 > ma)ma = v + 1;add_edge(u, v+1, 2);}for(int i = 1; i <= ma; i++){add_edge(i-1, i, 0);add_edge(i, i - 1, -1);}int ans = spfa(0, ma+1);cout << ans << endl;}return 0;
}