（一种比较朴素的解决方案，用C写的。之后会尝试用C++重写一遍）
根据题意使用链表抽象城市和道路，注意到这样的链表没有数据域，只需使用指针域，所以考虑使用数组模拟一个链表作为抽象道路。
一个自然的想法是将每次查询后的道路个数统计一遍以得出答案，然而这种写法的时间复杂度太高以至于运行过程中会发生时间超限（运行超时、TLE），因此需要转换思路。以下给出这个错误思路的答案：
// 这种做法会发生时间超限
int* shortestDistanceAfterQueries(int n, int** queries, int queriesSize, int* queriesColSize, int* returnSize) {
*returnSize = queriesSize;
int *answer = malloc(*returnSize * sizeof(int));
int *roads = malloc(n * sizeof(int));
for(int i=0;i<n;i++){
roads[i]=i+1;
}
for(int i=0;i<queriesSize;i++){
if(roads[queries[i][0]]<queries[i][1])roads[queries[i][0]]=queries[i][1];
answer[i]=0;
for(int j=0;roads[j]!=n;j=roads[j]){
answer[i]++;
}
}free(roads);
return answer;
}
显然，以上这种写法对每一个节点重复访问的次数过多，考虑对每次查询，计算拆除的道路数minus，每次查询后使用当前道路数减去(minus-1)（因为同时还新建了一条道路），由于每条道路只能拆除一次，可以有效降低重复访问的情况。
注意到题目指出，对于任意两个查询queries[i]、queries[i]，都不会满足 queries[i][0] < queries[j][0] < queries[i][1] < queries[j][1]，故任意两个查询间，只存在包含与被包含的关系，因此在某次查询中，此处我们记u = queries[i][0];、v = queries[i][1];，只需满足roads[u]>v或roads[u]==-1，即可认为本次查询已被包含于此前的查询中，以此构建循环条件。
对于区间(u, v)中的城市，将其指向-1以拆除道路，同时将roads[u]指向下一个城市，同时将拆除计数变量minus加一，当j>=v时循环退出，查询结束，如果有拆除的道路，将len减去其值并向answer计入。
以下给出这种思路的答案：
int* shortestDistanceAfterQueries(int n, int** queries, int queriesSize, int* queriesColSize, int* returnSize) {
*returnSize = queriesSize;
int *answer = malloc(*returnSize * sizeof(int));
int *roads = malloc(n * sizeof(int));
int len = n-1,minus=0;
for(int i=0;i<n;i++){
roads[i]=i+1;
}
int u,v,t;
for(int i=0;i<queriesSize;i++){
minus=0;
u = queries[i][0];
v = queries[i][1];
for(int j=u;j<v && v>roads[u] && roads[j]!=-1;){
t=roads[j];
roads[j]=-1;
roads[u]=t;
j=t;
minus++;
}
if(minus)len-=minus-1;
answer[i]=len;
}
free(roads);
return answer;
}
