题目:
1 #include2 #include 3 #include 4 #include 5 6 const int INF = 0x3f3f3f3f; 7 8 struct Edge 9 {10 int v, w;11 Edge(){};12 Edge(int v, int w)13 {14 this->v = v;15 this->w = w;16 }17 };18 19 std::vector map[10010];20 int dist[10010];21 bool inque[10010];22 23 void spfa(int s)24 {25 std::queue q;26 memset(inque, 0, sizeof(inque));27 dist[s] = 0;28 q.push(s);29 inque[s] = 1;30 while(!q.empty())31 {32 int u = q.front();33 q.pop();34 inque[u] = 0;35 for(int i = 0; i < map[u].size(); i++)36 {37 int v = map[u][i].v;38 if(dist[v] < dist[u] + map[u][i].w)39 {40 dist[v] = dist[u] + map[u][i].w;41 if(!inque[v])42 {43 q.push(v);44 inque[v] = 1;45 }46 }47 }48 }49 }50 51 int main()52 {53 int n;54 int x, y;55 while(scanf("%d", &n) != EOF)56 {57 for(int i = 0; i <= 10001; i++)58 {59 map[i].clear();60 }61 int low = INF, high = 0;62 for(int i = 0; i < n; i++)63 {64 scanf("%d %d", &x, &y);65 map[x].push_back(Edge(y+1, 2));66 if(low > x)low = x;67 if(high < y)high = y;68 }69 for(int i = low; i <= high+1; i++)70 {71 map[0].push_back(Edge(i, 0));72 map[i].push_back(Edge(i+1, 0));73 map[i+1].push_back(Edge(i, -1));74 dist[i] = -INF;75 }76 map[0].push_back(Edge(high+1, 0));77 spfa(low);78 printf("%d\n", dist[high+1] - dist[low]);79 }80 return 0;81 }