题意：一条直线上有n个点，标号从1到n，起点为0，终点为N+1，给定m个限制关系（ci，di），访问ci点前必须先访问di点，每两个点之间是单位距离，求在限制条件下，从起点到终点访问完所有的点的最短距离。
分析：画图模拟一下可知，从起点到终点的N+1这段距离是必须的，若想距离最短，必须去重。
比如以下样例，
10 3
3 7
8 9
2 5
试模拟一下按部就班的访问，从0开始，先访问5，再访问2，->7->3->9->8>11,最后结束，因为要满足限制条件，会重走一些路，有些重走是不可避免的，比如限制条件8 9,为了先访问9再访问8，必须将8~9这一段走2遍，但是限制条件2 5和3 7则不然，不必要将2~5和3~7都重走2遍，画图显然可知，只需将2~7重走2遍就可同时满足这两个限制条件，也就是说，如果两个限制条件走过的路有交叉（可能是包含）的话，那么取并集即可。
1 #include<cstdio> 2 #include<cstring> 3 #include<cstdlib> 4 #include<cctype> 5 #include<cmath> 6 #include<iostream> 7 #include<sstream> 8 #include<iterator> 9 #include<algorithm> 10 #include<string> 11 #include<vector> 12 #include<set> 13 #include<map> 14 #include<stack> 15 #include<deque> 16 #include<queue> 17 #include<list> 18 typedef long long ll; 19 typedef unsigned long long llu; 20 const int INT_INF = 0x3f3f3f3f; 21 const int INT_M_INF = 0x7f7f7f7f; 22 const ll LL_INF = 0x3f3f3f3f3f3f3f3f; 23 const ll LL_M_INF = 0x7f7f7f7f7f7f7f7f; 24 const int dr[] = {0, 0, -1, 1}; 25 const int dc[] = {-1, 1, 0, 0}; 26 const double pi = acos(-1.0); 27 const double eps = 1e-8; 28 const int MAXN = 1000 + 10; 29 const int MAXT = 20000 + 10; 30 using namespace std; 31 struct P 32 { 33 int x, y; 34 bool operator < (const P& a)const 35 { 36 return x < a.x || (x == a.x && y < a.y); 37 } 38 }; 39 int main() 40 { 41 int N, m; 42 while(scanf("%d%d", &N, &m) == 2) 43 { 44 if(m == 0) 45 { 46 printf("%d\n", N + 1); 47 continue; 48 } 49 int ans = N + 1; 50 P num[505]; 51 for(int i = 0; i < m; ++i) 52 scanf("%d%d", &num[i].x, &num[i].y); 53 sort(num, num + m); 54 int s = num[0].x; 55 int e = num[0].y; 56 for(int i = 1; i < m; ++i) 57 { 58 if(num[i].x > num[i].y) continue; 59 if(num[i].x >= s && num[i].y <= e) continue; 60 else if(num[i].x >= s && num[i].x <= e && num[i].y >= e) 61 e = num[i].y; 62 else 63 { 64 ans += 2 * (e - s); 65 s = num[i].x; 66 e = num[i].y; 67 } 68 } 69 ans += 2 * (e - s); 70 printf("%d\n", ans); 71 } 72 return 0; 73 }