题目

建立一个无向图，输入起点和终点，搜索最短路径并打印。 Example: Input: 4 1 2 1 3 1 4 2 5 1 1 5 Output: 2 1 2 5

代码

#include<iostream> #include<vector> using namespace std; vector<int> path,tmp; vector<int> v[1000]; bool visited[1000]; int minn,start,endi;; void dfs(int cur,int depth) { // if(visited[cur]) return; if(cur==endi) { if(minn>depth) { minn=depth; path=tmp; } return; } visited[cur]=true; for(int i:v[cur]) { if(!visited[i]) { visited[i]=true; tmp.emplace_back(i); dfs(i,depth+1); visited[i]=false; tmp.pop_back(); } } } int main() { int n,a,b; cin>>n; for(int i=0;i<n;i++) { cin>>a>>b; v[a].emplace_back(b); v[b].emplace_back(a); } cin>>n; for(int i=0;i<n;i++) { cin>>start>>endi; //fill(visited,visited+1000,false); minn=9999; path.clear(); path.emplace_back(start); visited[start]=true; dfs(start,0); visited[start]=false; cout<<minn<<endl; cout<<start<<endl; for(int each:path) cout<<each<<endl; } system("pause"); }