题解 CF20C 【Dijkstra?】

- 刚开始看以为是最短路的模板题，就直接用堆优化dijkstra+输出路径搞了一波。结果十分惨烈…… 这道题坑还是有的，比如： - 边是双向边（这一点翻译没有很好的说明） - 后边的数据大到要开long long 知道了这些后，这题就比较简单了，直接最短路+路径输出 就可以了 在下用的是堆优化dijkstra ```cpp #include<iostream> #include<algorithm> #include<queue> #include<cstdio> using namespace std; struct yyy{ int f, t, len, nex; }e[500100*2]; //前向星存图 struct node{ int x; long long y; bool operator < (const node& hhh) const{ return y>hhh.y; } //重载运算符实现小根堆 }; priority_queue <node> q; //STL大法好 int tot,head[100100]; void add(int x,int y,int z) //加边函数 { e[++tot].f=x; e[tot].t=y; e[tot].len=z; e[tot].nex=head[x]; head[x]=tot; } long long int dis[100100]; //一定要开long long int flag,ans[100100],pos[100100]; //存储路径 int main() { int n,m,s; cin>>n>>m; s=1; for(int i=1;i<=m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z); //双向边 add(y,x,z); } for(int i=1;i<=n;i++) dis[i]=9223372036854775806; dis[s]=0; ans[flag]=s; q.push(node{s,dis[s]}); while(!q.empty()) //dijkstra主体 { node ww=q.top(); q.pop(); int k=ww.x; if(ww.y!=dis[k]) continue; for(int j=head[k];j;j=e[j].nex) if(dis[e[j].t]>dis[k]+e[j].len) { dis[e[j].t]=dis[k]+e[j].len; q.push(node{e[j].t,dis[e[j].t]}); pos[e[j].t]=k; //存储路径 } } bool flag2=1; //判断能否找到起点 for(int i=n;i;i=pos[i]) //到着从终点找回去 { ans[++flag]=i; if(i==1) //如果找到起点，更改判断变量 flag2=0; } if(flag2){ cout<<-1; return 0; } //没有找到起点，输出"-1" for(int i=flag;i>=1;i--) //因为是倒着找回去的，所以要倒序输出 cout<<ans[i]<<" "; return 0; } ```