这题后台数据一定很坑，估计是那种从节点1可以扩展到节点2~19，但是就是无法与节点20连通的那种，才导致了刚开始没有逆向搜索的时候TLE到3000MS。
逆向DFS找到所有与终点相连的节点保存下来，速度很快的。这样正向搜索时就要把与终点不相连的节点剪枝。
判断连通性的方法有很多，其实本题还可以用BFS或者并查集防止超时。
#include#include #include #include #include #include using namespace std;int n, kase, cnt, vis[22], road[22][22];int join[22];vector res;void find_join(int u){ join[u] = 1; for(int v = 1; v <= 20; ++v) if (!join[v] && road[u][v]) find_join(v);}void DFS(int u){ if (u == n){ ++cnt; for (unsigned i = 0; i != res.size(); ++i) printf("%d%c", res[i], i==res.size()-1 ? '\n' : ' '); return; } for (int v = 1; v <= 20; ++v){ if (!vis[v] && road[u][v] && join[v]){ vis[v] = 1; res.push_back(v); DFS(v); vis[v] = 0; res.pop_back(); } }}void init(){ cnt = 0; memset(road, 0, sizeof(road)); memset(vis, 0, sizeof(vis)); memset(join, 0, sizeof(join)); vis[1] = 1; res.clear(); res.push_back(1);}int main(){ while (init(), cin >> n){ int x, y; while (cin >> x >> y, x || y) road[x][y] = road[y][x] = 1; printf("CASE %d:\n", ++kase); find_join(n); DFS(1); printf("There are %d routes from the firestation to streetcorner %d.\n", cnt, n); } return 0;}