C++地铁旅行：森森的认证照之旅 - 寻找所有可达站点

#include<iostream>\n#include<vector>\n#include<queue>\n#include<algorithm>\nusing\ namespace\ std;\n\nconst\ int\ INF\ =\ 1000000000;\n\nstruct\ Edge\ {\n int\ to,\ cost;\n};\n\ntypedef\ pair<int,\ int>\ P;\n\nint\ dijkstra(int\ start,\ int\ N,\ vector<vector<Edge>>&\ graph,\ vector<int>&\ dist)\ {\n priority_queue<P,\ vector<P>,\ greater<P>>\ que;\n dist[start]\ =\ 0;\n que.push(P(0,\ start));\n\n while\ (!que.empty()) {\n P\ p\ =\ que.top();\n que.pop();\n int\ v\ =\ p.second;\n if\ (dist[v]\ <\ p.first)\ continue;\n for\ (int\ i\ =\ 0;\ i\ <\ graph[v].size();\ i++)\ {\n Edge\ e\ =\ graph[v][i];\n if\ (dist[e.to]\ >\ dist[v]\ +\ e.cost)\ {\n dist[e.to]\ =\ dist[v]\ +\ e.cost;\n que.push(P(dist[e.to],\ e.to));\n } \n } \n } \n}\n\nint\ main()\ {\n int\ N,\ M,\ K;\n cin\ >>\ N\ >>\ M\ >>\ K;\n\n vector<vector<Edge>>\ graph(N);\n for\ (int\ i\ =\ 0;\ i\ <\ M;\ i++)\ {\n int\ X;\n cin\ >>\ X;\n vector<int>\ stations(X);\n for\ (int\ j\ =\ 0;\ j\ <\ X;\ j++)\ {\n cin\ >>\ stations[j];\n } \n for\ (int\ j\ =\ 0;\ j\ <\ X\ -\ 1;\ j++)\ {\n int\ cost;\n cin\ >>\ cost;\n graph[stations[j]\ -\ 1].push_back(Edge{stations[j\ +\ 1]\ -\ 1,\ cost});\n graph[stations[j\ +\ 1]\ -\ 1].push_back(Edge{stations[j]\ -\ 1,\ cost});\n } \n } \n\n int\ Q;\n cin\ >>\ Q;\n vector<int>\ startStations(Q);\n for\ (int\ i\ =\ 0;\ i\ <\ Q;\ i++)\ {\n cin\ >>\ startStations[i];\n } \n\n for\ (int\ i\ =\ 0;\ i\ <\ Q;\ i++)\ {\n vector<int>\ dist(N,\ INF);\n dijkstra(startStations[i]\ -\ 1,\ N,\ graph,\ dist);\n vector<int>\ reachableStations;\n for\ (int\ j\ =\ 0;\ j\ <\ N;\ j++)\ {\n if\ (dist[j]\ <=\ K)\ {\n reachableStations.push_back(j\ +\ 1);\n } \n } \n sort(reachableStations.begin(),\ reachableStations.end());\n for\ (int\ j\ =\ 0;\ j\ <\ reachableStations.size();\ j++)\ {\n cout\ <<\ reachableStations[j]\ <<\ " ";\n } \n cout\ <<\ endl;\n } \n\n return\ 0;\n} \n