完全就是理解题意的问题....
他的题目可以简化成一下：
有n个点，m条边。要求从0到达1，输出路径。
但是对于每个点，你不允许从这个点走 “此点到达1点的最短路所经过的那个边”。
如果你到达了2点。2点指向3，4，5. 如果2点到达1点的最短路经过了3点，也就是走了2->3
这条边，那么你就不能走这条边。你只能走4，5这两个点。
所以我们第一步肯定是要求出所有点到达1点的最短路，所经过的第一个点求出来。
也就是反向求最短路，从1点到达其他所有点的最短路。记录一下最后一个点即可。
path【i】=j，也就代表你不能从i走到j。
因为你求最短路是，1是通过j走到i的，所以你是顺便记录了path[i]=j.
之后dfs从0开始dfs，记录路径搜索，不能走重复点，不能走path点。找到1即可。
#include<iostream>#include<cstdio>#include<cstring>#include<queue>#include<algorithm>#include<vector>#include<stack>using namespace std;const int maxn = 2e5+10;#define pa pair<int,int>struct node{ int from; int to; int next; int v;}edge[2*maxn];int cnt=0,head[maxn],n;int dis[maxn];int vis[maxn];int path[maxn];int f;int m;int INF=0x3f3f3f3f;stack<int>st;int flag;void add(int u,int v,int w){ cnt++; edge[cnt].to=v; edge[cnt].next=head[u]; edge[cnt].v=w; edge[cnt].from=u; head[u]=cnt;}void dijkstra(){ priority_queue<pa,vector<pa>,greater<pa> >q; for (int i=1;i<n;i++) dis[i]=INF; dis[1]=0; q.push(make_pair(0,1)); while (!q.empty()) { int now=q.top().second; q.pop(); for (int i=head[now];i!=-1;i=edge[i].next) { int longg=dis[now]+edge[i].v; if(longg<dis[edge[i].to]) { dis[edge[i].to]=longg; path[edge[i].to]=now;//如果1经过2为最短路，那么path【2】=1.代表2不能到达1，这条路属于最短路的一部分，不可以走 q.push(make_pair(dis[edge[i].to],edge[i].to)); } } }}void dfs(int id,int father){ if(flag) return ; st.push(id); vis[id]=1; if(id==1) { vector<int>ans; while(!st.empty()) ans.push_back(st.top()),st.pop(); reverse(ans.begin(),ans.end()); int len = ans.size(); cout<<len; for(int i=0; i<len; i++) cout<<" "<<ans[i]; cout<<endl; flag = 1; return; } for(int i=head[id];i!=-1;i=edge[i].next) { int mubiao=edge[i].to; if(vis[mubiao]||path[id]==mubiao)//不能走重复点（题目要求），并且不能走最短路的点。 continue; dfs(mubiao,id); if(flag) return ; } st.pop();}int main(){ memset(head,-1,sizeof(head)); memset(dis,INF,sizeof(dis)); memset(path,-1,sizeof(path)); cin>>n>>m; for(int i=0;i<m;i++) { int u,v,w; cin>>u>>v>>w; add(u,v,w); add(v,u,w); } dijkstra();//反向求最短路 /* for(int i=0;i<n;i++) { cout<<dis[i]<<endl; }*/ flag=0; memset(vis,0,sizeof(vis)); dfs(0,-1);//从0出发 if(!flag) cout<<"impossible"<<endl;}/*7 90 1 8006 2 3002 3 753 4 804 5 504 1 1001 6 350 2 1200 3 100*/
